In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent

A Kempe swap in a proper coloring interchanges the colors on some maximal connected 2-colored subgraph. Two k-colorings are k-equivalent if we can transform one into the other using Kempe swaps. The triangulated toroidal grid, T[m x n], is formed from (a toroidal embedding of) the Cartesian product of C-m and C-n by adding parallel diagonals inside all 4-faces. Mohar and Salas showed that not all 4-colorings of T[m x n] are 4-equivalent. In contrast, Bonamy, Bousquet, Feghali, and Johnson showed that all 6-colorings of T[m x n] are 6-equivalent. They asked whether the same is true for 5-colorings. We answer their question affirmatively when m, n >= 6. Further, we show that if G is 6-regular with a toroidal embedding where every non-contractible cycle has length at least 7, then all 5-colorings of G are 5-equivalent. Our results relate to the antiferromagnetic Pott's model in statistical mechanics. (c) 2022 Elsevier Ltd. All rights reserved.

Automated summary

A Kempe swap interchanges colors on some maximal connected 2-colored subgraph in a proper coloring. While not all 4-colorings of T[m x n] are 4-equivalent, all 6-colorings are 6-equivalent. We affirmatively answer the question of whether all 5-colorings of T[m x n] are 5-equivalent when m, n >= 6. Furthermore, we show that if G is 6-regular with a toroidal embedding where every non-contractible cycle has length at least 7, then all 5-colorings of G are 5-equivalent. These results are related to the antiferromagnetic Pott's model.