The Ramsey Numbers of Squares of Paths and Cycles

This is the authors' abstract. We don't add key points for this paper.

The square G² 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 KN 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 haveR(P₃ₙ²,P₃ₙ²)=R(P₃ₙ₊₁²,P₃ₙ₊₁²)=R(C₃ₙ²,C₃ₙ²)=9n-3 and R(P₃ₙ₊₂²,P₃ₙ₊₂²)=9n+1. We also show that for any γ>0 and Δ there exists β>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 Δ(G) of G is at most Δ, and G has bandwidth at most β n, then R(G,G)≤ (3+γ)n.