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 \geq 3, all kk-colourings of 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 cubic graph GG are Kempe equivalent unless GG is the complete graph K4K_4 or the triangular prism.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.