Feghali, C. and Johnson, M. and Paulusma, D. (2015) 'Kempe equivalence of colourings of cubic graphs.', Electronic notes in discrete mathematics., 49 . pp. 243-249.
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.
|Keywords:||Kempe equivalence, Cubic graph, Graph colouring.|
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (237Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.endm.2015.06.034|
|Publisher statement:||© 2015 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:||No date available|
|Date deposited:||21 August 2015|
|Date of first online publication:||November 2015|
|Date first made open access:||12 November 2016|
Save or Share this output
|Look up in GoogleScholar|