Kempe equivalence of colourings of cubic graphs. (January 2017)
- Record Type:
- Journal Article
- Title:
- Kempe equivalence of colourings of cubic graphs. (January 2017)
- Main Title:
- Kempe equivalence of colourings of cubic graphs
- Authors:
- Feghali, Carl
Johnson, Matthew
Paulusma, Daniël - Abstract:
- 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 K 4 or the triangular prism.
- Is Part Of:
- European journal of combinatorics. Volume 59(2017)
- Journal:
- European journal of combinatorics
- Issue:
- Volume 59(2017)
- Issue Display:
- Volume 59, Issue 2017 (2017)
- Year:
- 2017
- Volume:
- 59
- Issue:
- 2017
- Issue Sort Value:
- 2017-0059-2017-0000
- Page Start:
- 1
- Page End:
- 10
- Publication Date:
- 2017-01
- Subjects:
- Combinatorial analysis -- Periodicals
Analyse combinatoire -- Périodiques
Combinatorial analysis
Periodicals
Electronic journals
511.6 - Journal URLs:
- http://www.sciencedirect.com/science/journal/01956698 ↗
http://www.elsevier.com/journals ↗
http://www.idealibrary.com ↗
http://firstsearch.oclc.org ↗
http://firstsearch.oclc.org/journal=0195-6698;screen=info;ECOIP ↗ - DOI:
- 10.1016/j.ejc.2016.06.008 ↗
- Languages:
- English
- ISSNs:
- 0195-6698
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3829.728200
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 634.xml