Kempe equivalence of colourings of cubic graphs

详细信息    查看全文

• 作者：Carl Feghali ^{carl.feghali@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Matthew Johnson ^{matthew.johnson2@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Danië ; l Paulusma ^{daniel.paulusma@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：59
• 期：Complete
• 页码：1-10
• 全文大小：455 K

文摘

Given a graph G=(V,E)$G=(V,E)$ and a proper vertex colouring of G$G$, a Kempe chain is a subset of V$V$ that induces a maximal connected subgraph of G$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$k\ge 3$, all k$k$-colourings of connected k$k$-regular graphs that are not complete are Kempe equivalent. We address the case k=3$k=3$ by showing that all 3$3$-colourings of a connected cubic graph G$G$ are Kempe equivalent unless G$G$ is the complete graph K₄$K_4$ or the triangular prism.