Back to Search
Start Over
Kempe equivalence of colourings of cubic graphs
- Source :
- Electronic notes in discrete mathematics, 2015, Vol.49, pp.243-249 [Peer Reviewed Journal], European journal of combinatorics, 2017, Vol.59, pp.1-10 [Peer Reviewed Journal]
- Publication Year :
- 2015
- Publisher :
- Elsevier, 2015.
-
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 \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.<br />very minor changes
- Subjects :
- FOS: Computer and information sciences
Kempe chain
Discrete Mathematics (cs.DM)
Vertex connectivity
0102 computer and information sciences
01 natural sciences
Combinatorics
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
0101 mathematics
Cubic graph
Mathematics
Discrete mathematics
Conjecture
Kempe equivalence
Applied Mathematics
010102 general mathematics
Complete graph
Graph
Vertex (geometry)
Graph colouring
010201 computation theory & mathematics
Triangular prism
Combinatorics (math.CO)
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Electronic notes in discrete mathematics, 2015, Vol.49, pp.243-249 [Peer Reviewed Journal], European journal of combinatorics, 2017, Vol.59, pp.1-10 [Peer Reviewed Journal]
- Accession number :
- edsair.doi.dedup.....ec9dc410af01b4e9df913d268b0c8474
- Full Text :
- https://doi.org/10.1016/j.endm.2015.06.034