A note on the Size-Ramsey number of long subdivisions of graphs
Donadelli, Jair; Haxell, Penny E.; Kohayakawa, Yoshiharu; 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:
Журнал:
RAIRO - Theoretical Informatics and Applications
Дата:
2005
Аннотация:
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>.
238.2Кб