C. Feghali
Kempe equivalence of colourings of cubic graphs
Feghali, C.; Johnson, M.; Paulusma, D.
Authors
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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 ≥ 3, all k-colourings of connected k-regular graphs that are not complete are Kempe equivalent. We address the case k = 3 by showing that all 3-colourings of a connected cubic graph G are Kempe equivalent unless G is the complete graph K4 or the triangular prism.
Citation
Feghali, C., Johnson, M., & Paulusma, D. (2015). Kempe equivalence of colourings of cubic graphs. . https://doi.org/10.1016/j.endm.2015.06.034
Conference Name | European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), |
---|---|
Conference Location | Bergen, Norway |
Publication Date | Nov 12, 2015 |
Deposit Date | Aug 12, 2015 |
Publicly Available Date | Nov 12, 2016 |
Volume | 49 |
Pages | 243-249 |
Series Title | Electronic Notes in Discrete Mathematics |
Series ISSN | 1571-0653 |
DOI | https://doi.org/10.1016/j.endm.2015.06.034 |
Keywords | Kempe equivalence, Cubic graph, Graph colouring. |
Files
Accepted Conference Proceeding
(243 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search