C. Feghali
A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
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
Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper coloring by changing the color of one vertex. We show an analogue of Brooks' Theorem by proving that from any k-coloring, inline image, a Δ-coloring of G can be obtained by a sequence of inline image recolorings using only the original k colors unless – G is a complete graph or a cycle with an odd number of vertices, or – inline image, G is Δ-regular and, for each vertex v in G, no two neighbors of v are colored alike. We use this result to study the reconfiguration graph inline image of the k-colorings of G. The vertex set of inline image is the set of all possible k-colorings of G and two colorings are adjacent if they differ on exactly one vertex. We prove that for inline image, inline image consists of isolated vertices and at most one further component that has diameter inline image. This result enables us to complete both a structural and an algorithmic characterization for reconfigurations of colorings of graphs of bounded maximum degree.
Citation
Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 24, 2015 |
Online Publication Date | Oct 27, 2015 |
Publication Date | Dec 1, 2016 |
Deposit Date | Oct 31, 2015 |
Publicly Available Date | Mar 28, 2024 |
Journal | Journal of Graph Theory |
Print ISSN | 0364-9024 |
Electronic ISSN | 1097-0118 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 83 |
Issue | 4 |
Pages | 340-358 |
DOI | https://doi.org/10.1002/jgt.22000 |
Keywords | Graph coloring, Reconfigurations, Brooks’ Theorem. |
Files
Accepted Journal Article
(261 Kb)
PDF
Copyright Statement
This is the accepted version of the following article: Feghali, C., Johnson, M. and Paulusma, D. (2016), A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4): 340-358, which has been published in final form at http://dx.doi.org/10.1002/jgt.22000. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
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