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.
The algorithmic question of whether @math is connected for a given @math is addressed in @cite_3 @cite_9 , where it is shown that the problem is coNP-complete for @math and bipartite @math , but polynomial-time solvable for planar bipartite @math .
@cite_9 @cite_3
2103875227 2129794490
For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question : given G, how easily can we decide whether or not C3(G) is connected?We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which C3(G) is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time. 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.