The size Ramsey number of short subdivisions of bounded degree graphs |
| |
Authors: | Yoshiharu Kohayakawa,Troy Retter,Vojt ch R dl |
| |
Affiliation: | Yoshiharu Kohayakawa,Troy Retter,Vojtěch Rödl |
| |
Abstract: | For graphs G and F, write if any coloring of the edges of G with colors yields a monochromatic copy of the graph F. Suppose is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than edges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs. |
| |
Keywords: | probabilistic methods random graphs regularity method Size‐Ramsey numbers subdivisions of graphs |
|
|