@article { ,
title = {Kempe equivalence of colourings of cubic graphs},
abstract = {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.},
doi = {10.1016/j.ejc.2016.06.008},
issn = {0195-6698},
journal = {European Journal of Combinatorics},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {1-10},
publicationstatus = {Published},
publisher = {Elsevier},
volume = {59},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2017},
author = {Feghali, C. and Johnson, M. and Paulusma, D.}
}