Kempe equivalence of colourings of cubic graphs

Feghali, C.; Johnson, M.; Paulusma, D.

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.

Citation

Feghali, C., Johnson, M., & Paulusma, D. (2015, November). Kempe equivalence of colourings of cubic graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway

• Presentation Conference Type: Conference Paper (published)
• Conference Name: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
• Publication Date: Nov 12, 2015
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Nov 12, 2016
• Volume: 49
• Pages: 243-249
• Series Title: Electronic Notes in Discrete Mathematics
• Series ISSN: 1571-0653
• DOI: https://doi.org/10.1016/j.endm.2015.06.034
• Keywords: Kempe equivalence, Cubic graph, Graph colouring.
• Public URL: https://durham-repository.worktribe.com/output/1153140