The @math -colouring reconfiguration problem asks whether, for a given graph @math , two proper @math -colourings @math and @math of @math , and a positive integer @math , there exists a sequence of at most @math proper @math -colourings of @math which starts with @math and ends with @math and where successive colourings in the sequence differ on exactly one vertex of @math . We give a complete picture of the parameterized complexity of the @math -colouring reconfiguration problem for each fixed @math when parameterized by @math . First we show that the @math -colouring reconfiguration problem is polynomial-time solvable for @math , settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all @math , we show that the @math -colouring reconfiguration problem, when parameterized by @math , is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.
Finally, the study of the diameter of @math raises interesting questions. @cite_12 it is shown that every component of @math has diameter polynomial (in fact quadratic) in the size of @math . On the other hand, for @math , explicit constructions @cite_5 are given of graphs @math for which @math has at least one component with diameter exponential in the size of @math . It is known that if @math is a @math -degenerate graph then @math is connected and it is conjectured that in this case @math has diameter polynomial in the size of @math @cite_3 ; for graphs of treewidth @math the conjecture has been proved in the affirmative @cite_14 .
@cite_5 @cite_14 @cite_3 @cite_12
1982587570 2129794490 2097520314
Let k be an integer. Two vertex k-colorings of a graph are adjacent if they differ on exactly one vertex. A graph is k-mixing if any proper k-coloring can be transformed into any other through a sequence of adjacent proper k-colorings. Any graph is (tw+2)-mixing, where tw is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two (tw+2)-colorings is at most quadratic, a problem left open in (2012). Jerrum proved that any graph is k-mixing if k is at least the maximum degree plus two. We improve Jerrumʼs bound using the grundy number, which is the worst number of colors in a greedy coloring. For a positive integer k and a graph G, the k-colour graph of G, C"k(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k-colourings are joined by an edge in C"k(G) if they differ in colour on just one vertex of G. In this note some results on the connectedness of C"k(G) are proved. In particular, it is shown that if G has chromatic number k@? 2,3 , then C"k(G) is not connected. On the other hand, for k>=4 there are graphs with chromatic number k for which C"k(G) is not connected, and there are k-chromatic graphs for which C"k(G) is connected. 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 © 2011 Wiley Periodicals, Inc.