The size-Ramsey number of powers of bounded degree trees

Main Article Content

Sören Berger Yoshiharu Kohayakawa Giulia Satiko Maesaka Taísa Martins Walner Mendonça Guilherme Oliveira Mota Olaf Parczyk


Given an integer~$s \ge 1$, the \textit{$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 $k$th power of any $n$-vertex bounded degree tree is linear in~$n$.

Article Details

How to Cite
Berger, S., Kohayakawa, Y., Maesaka, G., Martins, T., Mendonça, W., Mota, G., & Parczyk, O. (2019). The size-Ramsey number of powers of bounded degree trees. Acta Mathematica Universitatis Comenianae, 88(3), 451-456. Retrieved from