Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200712May 2007 
Finding Paths Between Graph Colourings: PSPACEcompleteness and Superpolynomial Distances
Paul Bonsma and Luis Cereceda
Suppose we are given a graph G together with two proper vertex kcolourings 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 kcolouring of G? This decision problem is trivial for k=2, and decidable in polynomial time for k=3. Here we prove it is PSPACEcomplete for all k ≥ 4. In particular, we prove that the problem remains PSPACEcomplete for bipartite graphs, as well as for: (i) planar graphs and 4≤k≤6, and (ii) bipartite planar graphs and k=4. Moreover, the values of k in (i) and (ii) are tight, in the sense that for larger values of k, it is always possible to recolour α to β.We also exhibit, for every k ≥ 4, a class of graphs {G_{N,k} : N ∈ Ν}, together with two kcolourings for each G_{N,k}, such that the minimum number of recolouring steps required to transform the first colouring into the second is superpolynomial in the size of the graph: the minimum number of steps is Ω(2^{N}), whereas the size of G_{N} is O(N^{2}). This is in stark contrast to the k=3 case, where it is known that the minimum number of recolouring steps is at most quadratic in the number of vertices. We also show that a class of bipartite graphs can be constructed with this property, and that: (i) for 4≥k≥6 planar graphs and (ii) for k=4 bipartite planar graphs can be constructed with this property. This provides a remarkable correspondence between the tractability of the problem and its underlying structure.
A PDF file (214 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200712, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7494. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 