Page 1

Displaying 1 – 3 of 3

Showing per page

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

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Let T s H 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 s H .

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

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)

RAIRO - Theoretical Informatics and Applications

Let TsH 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 TsH.

Currently displaying 1 – 3 of 3

Page 1