Finding shortest paths between graph colourings.

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successive colourings in the sequence dier on exactly one vertex of G. We give a complete picture of the parameterized complexity of the k-colouring reconguration problem for each xed k when parameterized by `. First we show that the k-colouring reconguration problem is polynomial-time solvable for k = 3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all k 4, we show that the k-colouring reconguration problem, when parameterized by `, is xed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses