August 2015. arXiv: 1503.03430

Paper abstract bibtex

Paper abstract bibtex

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 {\textbackslash}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.

@unpublished{feghali_kempe_2015, title = {Kempe {Equivalence} of {Colourings} of {Cubic} {Graphs}}, url = {http://arxiv.org/abs/1503.03430}, 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 {\textbackslash}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.}, urldate = {2020-01-20}, author = {Feghali, Carl and Johnson, Matthew and Paulusma, Daniel}, month = aug, year = {2015}, note = {arXiv: 1503.03430}, keywords = {Computer Science - Discrete Mathematics, Mathematics - Combinatorics} }

Downloads: 0