Abstract
Given a graph and a proper vertex colouring of , a Kempe chain is a subset of that induces a maximal connected subgraph of 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 , all -colourings of -regular graphs that are not complete are Kempe equivalent. We address the case by showing that all -colourings of a cubic graph are Kempe equivalent unless is the complete graph or the triangular prism.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.