Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

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

Jair DonadelliPenny E. HaxellYoshiharu 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)