Publication details for Professor Matthew JohnsonFeghali, C., Johnson, M. & Paulusma, D. (2015), Kempe equivalence of colourings of cubic graphs, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Bergen, 243-249.
- Publication type: Conference Paper
- ISSN/ISBN: 1571-0653
- DOI: 10.1016/j.endm.2015.06.034
- Keywords: Kempe equivalence, Cubic graph, Graph colouring.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
Given a graph G = (V,E) and a proper vertex colouring of G, a Kempe chain is a
subset of V that induces a maximal connected subgraph of G in which every vertex
has one of two colours. To make a Kempe change is to obtain one colouring from
another by exchanging the colours of vertices in a Kempe chain. Two colourings
are Kempe equivalent if each can be obtained from the other by a series of Kempe
changes. A conjecture of Mohar asserts that, for k ≥ 3, all k-colourings of connected
k-regular graphs that are not complete are Kempe equivalent. We address the case
k = 3 by showing that all 3-colourings of a connected cubic graph G are Kempe
equivalent unless G is the complete graph K4 or the triangular prism.