RAIRO - Theoretical Informatics and Applications

Table of Contents - January 2005 - Volume 39, Issue 01 (Imre Simon, the tropical computer scientist)  

Research Article

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

Donadelli, Jaira1, Haxell, Penny E.a2 and Kohayakawa, Yoshiharua3

a1 Departamento de Informática, Universidade Federal do Paraná, Centro Politécnico Caixa Postal 19081, 81531-980 Curitiba PR, Brasil; e-mail: 

a2 Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada; e-mail: 

a3 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: 

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 .

(Online publication March 15 2005)

Key Words:

  • The Size-Ramsey number;
  • Ramsey theory;
  • expanders;
  • Ramanujan graphs;
  • explicit constructions.

Mathematics Subject Classification:

  • 05C55;
  • 05D40