The size Ramsey number of short subdivisions of bounded degree graphs
- 12 July 2018
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 54 (2) , 304-339
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
Funding Information
- FAPESP (2013/03447‐6)
- CNPq (310974/2013‐5, 459335/2014‐6)
- National Science Foundation (DMS 1301698, DMS 1102086, 1764385)
This publication has 20 references indexed in Scilit:
- An Alternative Proof of the Linearity of the Size-Ramsey Number of PathsCombinatorics, Probability and Computing, 2014
- The size‐Ramsey number of treesRandom Structures & Algorithms, 2011
- Small subsets inherit sparse ε-regularityJournal of Combinatorial Theory, Series B, 2007
- Random Graphs2001
- Hall's theorem for hypergraphsJournal of Graph Theory, 2000
- The size-Ramsey number of treesIsrael Journal of Mathematics, 1995
- Expanding graphs contain all small treesCombinatorica, 1987
- On size Ramsey number of paths, trees, and circuits. IJournal of Graph Theory, 1983
- On the combinatorial problems which I would most like to see solvedCombinatorica, 1981
- The size Ramsey numberPeriodica Mathematica Hungarica, 1978