The multicolour size-Ramsey number of powers of paths

Abstract

Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $G\to (H{)}_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number ${\hat{r}}_s(H)$ of a graph $H$ is defined to be ${\hat{r}}_s(H)=\min \{|E(G)|:G\to (H{)}_s\}$. We prove that, for all positive integers $k$ and $s$, we have ${\hat{r}}_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$.

15 pages