Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 191 - 206 DOI 10.1051/ita:2005019

Theoret. Informatics Appl. 39, 191-206 (2005)
DOI: 10.1051/ita:2005019

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli¹, Penny E. Haxell² and Yoshiharu Kohayakawa<sup>3

1</sup>  Departamento de Informática, Universidade Federal do Paraná, Centro Politécnico Caixa Postal 19081, 81531-980 Curitiba PR, Brasil;
    e-mail: jair@inf.ufpr.br
²  Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada;
    e-mail: pehaxell@math.uwaterloo.ca
³  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: yoshi@ime.usp.br

Abstract
Let  T_sH 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_sH.

Mathematics Subject Classification. 05C55, 05D40

Key words: The Size-Ramsey number -- Ramsey theory -- expanders -- Ramanujan graphs -- explicit constructions.


© EDP Sciences 2005

What is OpenURL?