We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Bonamy, Marthe and Bousquet, Nicolas and Feghali, Carl and Johnson, Matthew (2019) 'On a conjecture of Mohar concerning Kempe equivalence of regular graphs.', Journal of combinatorial theory, series B., 135 . pp. 179-199.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:10 August 2018
Date deposited:13 August 2018
Date of first online publication:16 August 2018
Date first made open access:16 August 2019

Save or Share this output

Look up in GoogleScholar