In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent

Daniel W. Cranston, Reem Mahmoud

Published 2021-02-16Version 1

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$.