Colouring Reconfiguration Is Fixed-Parameter Tractable ⋆
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh S. Patel, Daniël Paulusma · 2014
We prove that the problem of determining whether there exists a path of length at most l between two given k-colourings in the reconfiguration graph for k-Colouring is fixed-parameter tractable for all fixed k � 1, when parameterized by l. This addresses an open problem of Mouawad, Nishimura, Raman, Simjour and Suzuki (IPEC 2013). We also show that the problem, when parameterized by l, even has a linear vertex kernel for k = 3 and no polynomial kernel for all k � 4 unless the polynomial hierarchy collapses.