Resource title

Finding paths between 3-colorings

Resource image

image for OpenScout resource :: Finding paths between 3-colorings

Resource description

Given a 3-colorable graph G together with two proper vertex 3-colorings alpha and beta of G, consider the following question: is it possible to transform alpha into beta 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, alpha, beta where the transformation is possible; the proof of this characterization is via an algorithm that either finds a sequence of recolorings between alpha and beta, 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(vertical bar V(G)vertical bar(2)) recoloring steps and in many cases returns a shortest sequence of recolorings. We also exhibit a class of instances G, alpha, beta that require Omega(vertical bar V(G)vertical bar(2)) recoloring steps.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/36005/

Resource license