We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

Johnson, M., Kratsch, D., Kratsch, S., Patel, V. & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica 75(2): 295-321.

Author(s) from Durham


The k -colouring reconfiguration 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 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 ℓ . 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≥4 , we show that the k -colouring reconfiguration problem, when parameterized by ℓ , 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.