Skip to main content

Research Repository

Advanced Search

On a conjecture of Mohar concerning Kempe equivalence of regular graphs

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

On a conjecture of Mohar concerning Kempe equivalence of regular graphs Thumbnail


Authors

Marthe Bonamy

Nicolas Bousquet

Carl Feghali



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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations