Kempe equivalence of colourings of cubic graphs. (January 2017)

• Record Type: Journal Article
• Authors: Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
• Is Part Of: European journal of combinatorics. Volume 59(2017)
• Page Start: 1
• Page End: 10
• Publication Date: 2017-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.06.008
• Languages: English
• ISSNs: 0195-6698

Abstract

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 K 4 or the triangular prism.