Finding paths between 3-colorings

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

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.
• Public URL: https://durham-repository.worktribe.com/output/1532604