Finding paths between 3‐colorings

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. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 69‐82, 2011