Finding Shortest Paths Between Graph Colourings

The $$k$$k-colouring reconfiguration problem asks whether, for a given graph $$G$$G, two proper $$k$$k-colourings $$\alpha $$ź and $$\beta $$β of $$G$$G, and a positive integer $$\ell $$l, there exists a sequence of at most $$\ell +1$$l+1 proper $$k$$k-colourings of $$G$$G which starts with $$\alpha $$ź and ends with $$\beta $$β and where successive colourings in the sequence differ on exactly one vertex of $$G$$G. We give a complete picture of the parameterized complexity of the $$k$$k-colouring reconfiguration problem for each fixed $$k$$k when parameterized by $$\ell $$l. First we show that the $$k$$k-colouring reconfiguration problem is polynomial-time solvable for $$k=3$$k=3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $$k \ge 4$$kź4, we show that the $$k$$k-colouring reconfiguration problem, when parameterized by $$\ell $$l, 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.