The size Ramsey number of short subdivisions of bounded degree graphs. Issue 2 (12th July 2018) - Kohayakawa, Yoshiharu; Retter, Troy; Rödl, Vojtěch
Abstract: For graphs G and F, write G → ( F ) ℓ if any coloring of the edges of G with ℓ colors yields a monochromatic copy of the graph F . Suppose S ( h ) 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 ( log ⁡ s ) 20 h s 1 + 1 / ( h + 1 ) edges for which G → ( S ( h ) ) ℓ holds, provided that s ≥ s 0 ( h, d, ℓ ) . 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.