Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

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 .

Page 1

Download Results (CSV)