Publication details for Professor Matthew JohnsonJohnson, M., Kratsch, D., Kratsch, S., Patel, V. & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica 75(2): 295-321.
- Publication type: Journal Article
- ISSN/ISBN: 0178-4617 (print), 1432-0541 (electronic)
- DOI: 10.1007/s00453-015-0009-7
- Keywords: Graph colouring, Graph algorithms, Reconfigurations, Reconfiguration graphs, Fixed parameter tractability.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
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.