The size-Ramsey number of powers of bounded degree trees
Given a positive integer (Formula presented.), the (Formula presented.) -colour size-Ramsey number of a graph (Formula presented.) is the smallest integer (Formula presented.) such that there exists a graph (Formula presented.) with (Formula presented.) edges with the property that, in any colouring of (Formula presented.) with (Formula presented.) colours, there is a monochromatic copy of (Formula presented.). We prove that, for any positive integers (Formula presented.) and (Formula presented.), the (Formula presented.) -colour size-Ramsey number of the (Formula presented.) th power of any (Formula presented.) -vertex bounded degree tree is linear in (Formula presented.). As a corollary, we obtain that the (Formula presented.) -colour size-Ramsey number of (Formula presented.) -vertex graphs with bounded treewidth and bounded degree is linear in (Formula presented.), which answers a question raised by Kamčev, Liebenau, Wood and Yepremyan.
| Item Type | Article |
|---|---|
| Copyright holders | © 2020 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1112/jlms.12408 |
| Date Deposited | 10 Jan 2022 |
| Acceptance Date | 2020 |
| URI | https://researchonline.lse.ac.uk/id/eprint/113369 |
Explore Further
- https://www.scopus.com/pages/publications/85098152461 (Scopus publication)
- https://londmathsoc.onlinelibrary.wiley.com/journa... (Official URL)