Back to Search
Start Over
In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent
- Source :
- European J. Combinatorics Vol. 104: 103532 (2022)
- Publication Year :
- 2021
-
Abstract
- 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\times 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\times n]$ are 4-equivalent. In contrast, Bonamy, Bousquet, Feghali, and Johnson showed that all 6-colorings of $T[m\times n]$ are 6-equivalent. They asked whether the same is true for 5-colorings. We answer their question affirmatively when $m,n\ge 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.<br />Comment: 17 pages, 16 figures; 4th version incorporates minor referee feedback; to appear in European Journal of Combinatorics
- Subjects :
- Mathematics - Combinatorics
05C15, 05C10
Subjects
Details
- Database :
- arXiv
- Journal :
- European J. Combinatorics Vol. 104: 103532 (2022)
- Publication Type :
- Report
- Accession number :
- edsarx.2102.07948
- Document Type :
- Working Paper