{
  "id": "2212.14860",
  "version": "v1",
  "published": "2022-12-30T18:20:56.000Z",
  "updated": "2022-12-30T18:20:56.000Z",
  "title": "The Ramsey numbers of squares of paths and cycles",
  "authors": [
    "Peter Allen",
    "Domenico Mergoni Cecchelli",
    "Barnaby Roberts",
    "Jozef Skokan"
  ],
  "categories": [
    "math.CO"
  ],
  "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-30T18:20:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ramsey number",
      "maximum degree",
      "blue copy",
      "complete graph",
      "colour classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}