| Автор | Donadelli, Jair |
| Автор | Haxell, Penny E. |
| Автор | Kohayakawa, Yoshiharu |
| Дата выпуска | 2005 |
| dc.description | Let T <sub> sH </sub> be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to T <sub> sH </sub>. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 2005 |
| Тема | The Size-Ramsey number |
| Тема | Ramsey theory |
| Тема | expanders |
| Тема | Ramanujan graphs |
| Тема | explicit constructions. |
| Название | A note on the Size-Ramsey number of long subdivisions of graphs |
| Тип | research-article |
| DOI | 10.1051/ita:2005019 |
| Electronic ISSN | 1290-385X |
| Print ISSN | 0988-3754 |
| Журнал | RAIRO - Theoretical Informatics and Applications |
| Том | 39 |
| Первая страница | 191 |
| Последняя страница | 206 |
| Аффилиация | Donadelli Jair; Departamento de Informática, Universidade Federal do Paraná, Centro Politécnico Caixa Postal 19081, 81531-980 Curitiba PR, Brasil; e-mail: |
| Аффилиация | Haxell Penny E.; Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada; e-mail: |
| Аффилиация | Kohayakawa Yoshiharu; Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo SP, Brasil; e-mail: |
| Выпуск | 1 |
