The Ramsey Numbers of Squares of Paths and Cycles

Abstract

The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in $G$. Given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum $N$ such that whenever the edges of the complete graph $K_N$ are coloured with red and blue, there exists either a red copy of $G$ or a blue copy of $H$.

We prove that for all sufficiently large $n$ we have
$$ R(P_{3n}^2,P_{3n}^2)=R(P_{3n+1}^2,P_{3n+1}^2)=R(C_{3n}^2,C_{3n}^2)=9n-3\mbox{ and } R(P_{3n+2}^2,P_{3n+2}^2)=9n+1.$$

We also show that for any $\gamma>0$ and $\Delta$ there exists $\beta>0$ such that the following holds: If $G$ can be coloured with three colours such that all colour classes have size at most $n$, the maximum degree $\Delta(G)$ of $G$ is at most $\Delta$, and $G$ has bandwidth at most $\beta n$, then $R(G,G)\le (3+\gamma)n$.