2015/10/23 by Bonamy, Marthe, Bousquet, Nicolas, Feghali, Carl +1 · 3 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1510.06964
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 k ≥ 3, 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 K4 nor the triangular prism are Kempe equivalent. In this paper, we prove that the conjecture holds for each k≥ 4. 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.