Premium
Finding paths between 3‐colorings
Author(s) -
Cereceda Luis,
van den Heuvel Jan,
Johnson Matthew
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20514
Subject(s) - combinatorics , vertex (graph theory) , mathematics , graph , sequence (biology) , time complexity , class (philosophy) , discrete mathematics , computer science , artificial intelligence , genetics , biology
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