Finding Shortest Paths between Graph Colourings
  The $k$-colouring reconfiguration problem asks whether, for a given graph $G$, two proper $k$-colourings $\alpha$ and $\beta$ of $G$, and a positive integer $\ell$, there exists a sequence of at most $\ell+1$ proper $k$-colourings of $G$ which starts with $\alpha$ and ends with $\beta$ and where successive colourings in the sequence differ on exactly one vertex of $G$. We give a complete picture of the parameterized complexity of the $k$-colouring reconfiguration problem for each fixed $k$ when parameterized by $\ell$. First we show that the $k$-colouring reconfiguration problem is polynomial-time solvable for $k=3$, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $k \geq 4$, we show that the $k$-colouring reconfiguration problem, when parameterized by $\ell$, 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. 
Matthew Johnson and Dieter Kratsch and Stefan Kratsch and Viresh Patel   and Dani\"el Paulusma
cs.CC cs.DS