On a conjecture of Mohar concerning Kempe equivalence of regular graphs

Bonamy, Marthe; Bousquet, Nicolas; Feghali, Carl; Johnson, Matthew

Abstract

Let G be a graph with a vertex colouring α. Let a and b be two colours. Then a connected component of the subgraph induced by those vertices coloured either a or b is known as a Kempe chain. A colouring of G obtained from α by swapping the colours on the vertices of a Kempe chain is said to have been obtained by a Kempe change. Two colourings of G are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. A conjecture of Mohar (2007) asserts that, for , all k-colourings of a k-regular graph that is not complete are Kempe equivalent. It was later shown that all 3-colourings of a cubic graph that is neither nor the triangular prism are Kempe equivalent. In this paper, we prove that the conjecture holds for each . We also report the implications of this result on the validity of the Wang–Swendsen–Kotecký algorithm for the antiferromagnetic Potts model at zero-temperature.

Citation

Bonamy, M., Bousquet, N., Feghali, C., & Johnson, M. (2019). On a conjecture of Mohar concerning Kempe equivalence of regular graphs. Journal of Combinatorial Theory, Series B, 135, 179-199. https://doi.org/10.1016/j.jctb.2018.08.002

• Journal Article Type: Article
• Acceptance Date: Aug 10, 2018
• Online Publication Date: Aug 16, 2018
• Publication Date: Mar 31, 2019
• Deposit Date: Aug 10, 2018
• Publicly Available Date: Aug 16, 2019
• Journal: Journal of Combinatorial Theory, Series B
• Print ISSN: 0095-8956
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 135
• Pages: 179-199
• DOI: https://doi.org/10.1016/j.jctb.2018.08.002
• Public URL: https://durham-repository.worktribe.com/output/1323810