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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (347Kb)
|Publisher Web site:||https://doi.org/10.1016/j.jctb.2018.08.002|
|Publisher statement:||© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|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|