The size‐Ramsey number of short subdivisions
METADATA ONLY
Loading...
Author / Producer
Date
2021-08
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The r-size-Ramsey number (R) over cap (r)(H) of a graph H is the smallest number of edges a graph G can have such that for every edge-coloring of G with r colors there exists a monochromatic copy of H in G. For a graph H, we denote by H-q the graph obtained from H by subdividing its edges with q - 1 vertices each. In a recent paper of Kohayakawa, Retter and Rodl, it is shown that for all constant integers q, r >= 2 and every graph H on n vertices and of bounded maximum degree, the r-size-Ramsey number of H-q is at most (log n)(20(q-1))n(1+1/q), for n large enough. We improve upon this result using a significantly shorter argument by showing that (R) over cap (r)(H-q) <= O(n(1+1/q)) for any such graph H.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
59 (1)
Pages / Article No.
68 - 78
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Ramsey theory; random graphs; subdivisions