Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653192 | European Journal of Combinatorics | 2017 | 10 Pages |
Abstract
Given a graph G=(V,E)G=(V,E) and a proper vertex colouring of GG, a Kempe chain is a subset of VV that induces a maximal connected subgraph of GG 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≥3k≥3, all kk-colourings of connected kk-regular graphs that are not complete are Kempe equivalent. We address the case k=3k=3 by showing that all 33-colourings of a connected cubic graph GG are Kempe equivalent unless GG is the complete graph K4K4 or the triangular prism.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Carl Feghali, Matthew Johnson, Daniël Paulusma,