The Ramsey Numbers of Squares of Paths and Cycles

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 have R (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.