The Ramsey numbers of squares of paths and cycles

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 (Formula presented). We also show that for every γ > 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 of G is at most ∆, and G has bandwidth at most βn, then R(G, G) ≤ (3 + γ)n.