Finding Paths between Graph Colourings: Computational Complexity and Possible Distances

Suppose we are given a graph G together with two proper vertex k-colourings of G, α and β. How easily can we decide whether it is possible to transform α into β by recolouring vertices of G one at a time, making sure we always have a proper k-colouring of G? ve a dichotomy theorem for the computational complexity of this decision problem: for values of k ⩽ 3 the problem is polynomial-time solvable, while for any fixed k ⩾ 4 it is PSPACE-complete. What is more, we establish a connection between the complexity of the problem and its underlying structure: we prove that for k ⩽ 3 the minimum number of necessary recolourings is polynomial in the size of the graph, while for k ⩾ 4 instances exist where this number is superpolynomial.