Feghali, C. and Johnson, M. and Paulusma, D. (2017) 'Kempe equivalence of colourings of cubic graphs.', European journal of combinatorics., 59 . pp. 1-10.
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (278Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1016/j.ejc.2016.06.008 |
| Publisher statement: | © 2016 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: | 29 June 2016 |
| Date deposited: | 30 June 2016 |
| Date of first online publication: | 22 July 2016 |
| Date first made open access: | 22 January 2017 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
