Kempe Equivalence of Colourings of Cubic Graphs. Feghali, C., Johnson, M., & Paulusma, D. August 2015. arXiv: 1503.03430
Kempe Equivalence of Colourings of Cubic Graphs [link]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