Publication details for Professor Matthew JohnsonCereceda, Luis, van den Heuvel, Jan & Johnson, Matthew (2011). Finding paths between 3-colorings. Journal of Graph Theory 67(1): 69-82.
- Publication type: Journal Article
- ISSN/ISBN: 0364-9024 (print), 1097-0118 (online)
- DOI: 10.1002/jgt.20514
- Keywords: Graph coloring, Algorithms, Graph recoloring, Reconfigurations.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.