The size-Ramsey number of powers of bounded degree trees

Berger, S., Kohayakawa, Y., Maesaka, G. S., Martins, T., Mendonça, W., Mota, G. O. & Parczyk, O. (2021). The size-Ramsey number of powers of bounded degree trees. Journal of the London Mathematical Society, 103(4), 1314 - 1332. https://doi.org/10.1112/jlms.12408
Copy

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.

picture_as_pdf

subject
Accepted Version

Download

Export as

EndNote BibTeX Reference Manager Refer Atom Dublin Core JSON Multiline CSV
Export