{
  "id": "2102.07948",
  "version": "v1",
  "published": "2021-02-16T04:01:06.000Z",
  "updated": "2021-02-16T04:01:06.000Z",
  "title": "In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent",
  "authors": [
    "Daniel W. Cranston",
    "Reem Mahmoud"
  ],
  "comment": "17 pages, 16 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A Kempe swap in a properly colored graph recolors one component of the subgraph induced by two colors, interchanging them on that component. Two $k$-colorings are Kempe $k$-equivalent if we can transform one into the other by a sequence of Kempe swaps, such that each intermediate coloring uses at most $k$ colors. Meyniel proved that if $G$ is planar, then all 5-colorings of $G$ are Kempe 5-equivalent; this proof relies heavily on the fact that planar graphs are 5-degenerate. To prove an analogous result for toroidal graphs would require handling 6-regular graphs. That is the focus of this paper. We show that if $G$ is a 6-regular graph that has an embedding in the torus with every non-contractible cycle of length at least 7, then all 5-colorings of $G$ are Kempe 5-equivalent. Bonamy, Bousquet, Feghali, and Johnson asked specifically about the case that $G$ is a triangulated toroidal grid, which is formed from the Cartesian product of $C_m$ and $C_n$ by adding a diagonal inside each 4-face, with all diagonals parallel. By slightly modifying the proof of our main result, we answer their question affirmatively when $m\\ge 6$ and $n\\ge 6$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-02-16T04:01:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C10"
    ],
    "keywords": [
      "toroidal graphs",
      "kempe equivalent",
      "kempe swap",
      "main result",
      "proof relies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}