Back to Search Start Over

Kempe equivalence of colourings of cubic graphs

Authors :
Daniël Paulusma
Carl Feghali
Matthew Johnson
Source :
Electronic notes in discrete mathematics, 2015, Vol.49, pp.243-249 [Peer Reviewed Journal], European journal of combinatorics, 2017, Vol.59, pp.1-10 [Peer Reviewed Journal]
Publication Year :
2015
Publisher :
Elsevier, 2015.

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 \geq 3$, all $k$-colourings of $k$-regular graphs that are not complete are Kempe equivalent. We address the case $k=3$ by showing that all $3$-colourings of a cubic graph $G$ are Kempe equivalent unless $G$ is the complete graph $K_4$ or the triangular prism.<br />very minor changes

Details

Database :
OpenAIRE
Journal :
Electronic notes in discrete mathematics, 2015, Vol.49, pp.243-249 [Peer Reviewed Journal], European journal of combinatorics, 2017, Vol.59, pp.1-10 [Peer Reviewed Journal]
Accession number :
edsair.doi.dedup.....ec9dc410af01b4e9df913d268b0c8474
Full Text :
https://doi.org/10.1016/j.endm.2015.06.034