The size-Ramsey number of powers of bounded degree trees

Author(s)

Berger, Soeren ^[1] ; Kohayakawa, Yoshiharu ^[2] ; Maesaka, Giulia Satiko ^[1] ; Martins, Taisa ^[3] ; Mendonca, Walner ^[4] ; Mota, Guilherme Oliveira ^[2] ; Parczyk, Olaf ^[5]

Affiliation

^[1] Univ Hamburg, Fachbereich Math, Bundesstr 55, D-20146 Hamburg - Germany

^[2] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil

^[3] Univ Fed Fluminense, Inst Matemat & Estat, BR-24210200 Niteroi, RJ - Brazil

^[4] IMPA, Jardim Bot, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro - Brazil

^[5] London Sch Econ, Dept Math, Houghton St, London WC2A 2AE - England

• Document type: Journal article
• Source: JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES; v. 103, n. 4 DEC 2020.
• Web of Science Citations: 1

Abstract

Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges with the property that, in any colouring of E(G) with s colours, there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex bounded degree tree is linear in n. As a corollary, we obtain that the s-colour size-Ramsey number of n-vertex graphs with bounded treewidth and bounded degree is linear in n, which answers a question raised by Kamcev, Liebenau, Wood and Yepremyan. (AU)

• FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Research Grants - Young Investigators Grants