The size-Ramsey number of powers of bounded degree trees

Abstract

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$.