Skip to main content

Research Repository

Advanced Search

Finding Shortest Paths Between Graph Colourings

Johnson, M.; Kratsch, D.; Kratsch, S.; Patel, V.; Paulusma, D.

Finding Shortest Paths Between Graph Colourings Thumbnail


D. Kratsch

S. Kratsch

V. Patel


The k-colouring reconguration 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 dier on exactly one vertex of G. We give a complete picture of the parameterized complexity of the k-colouring reconguration problem for each xed k when parameterized by `. First we show that the k-colouring reconguration 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 reconguration problem, when parameterized by `, is xed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.


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

Journal Article Type Article
Acceptance Date Apr 30, 2015
Online Publication Date May 12, 2015
Publication Date Jun 1, 2016
Deposit Date May 25, 2015
Publicly Available Date May 12, 2016
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 75
Issue 2
Pages 295-321
Keywords Graph colouring, Graph algorithms, Reconfigurations, Reconfiguration graphs, Fixed parameter tractability.


You might also like

Downloadable Citations