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. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1002/rsa.20995 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | DocType | Volume |
Ramsey theory, random graphs, subdivisions | Journal | 59 |
Issue | ISSN | Citations |
1 | 1042-9832 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Draganić Nemanja | 1 | 0 | 0.68 |
michael krivelevich | 2 | 1688 | 179.90 |
Rajko Nenadov | 3 | 33 | 8.69 |