Skip to main content

Research Repository

Advanced Search

Finding paths between 3-colorings

Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew

Authors

Luis Cereceda

Jan van den Heuvel



Abstract

Given a 3-colorable graph G together with two proper vertex 3-colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are proper 3-colorings? We prove that this question is answerable in polynomial time. We do so by characterizing the instances G, α, β where the transformation is possible; the proof of this characterization is via an algorithm that either finds a sequence of recolorings between α and β, or exhibits a structure which proves that no such sequence exists. In the case that a sequence of recolorings does exist, the algorithm uses O(|V(G)|2) recoloring steps and in many cases returns a shortest sequence of recolorings. We also exhibit a class of instances G, α, β that require Ω(|V(G)|2) recoloring steps

Citation

Cereceda, L., van den Heuvel, J., & Johnson, M. (2011). Finding paths between 3-colorings. Journal of Graph Theory, 67(1), 69-82. https://doi.org/10.1002/jgt.20514

Journal Article Type Article
Publication Date May 1, 2011
Deposit Date Dec 19, 2011
Journal Journal of Graph Theory
Print ISSN 0364-9024
Electronic ISSN 1097-0118
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 67
Issue 1
Pages 69-82
DOI https://doi.org/10.1002/jgt.20514
Keywords Graph coloring, Algorithms, Graph recoloring, Reconfigurations.


You might also like



Downloadable Citations