Finding Paths between Graph Colourings: Computational Complexity and Possible Distances

Bonsma, Paul; Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew

doi:10.1016/j.endm.2007.07.073

Finding Paths between Graph Colourings: Computational Complexity and Possible Distances

Bonsma, Paul; Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew

Authors

Paul Bonsma

Luis Cereceda

Jan van den Heuvel

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Abstract

Suppose we are given a graph G together with two proper vertex k-colourings of G, α and β. How easily can we decide whether it is possible to transform α into β by recolouring vertices of G one at a time, making sure we always have a proper k-colouring of G? We prove a dichotomy theorem for the computational complexity of this decision problem: for values of k⩽3 the problem is polynomial-time solvable, while for any fixed k⩾4 it is PSPACE-complete. What is more, we establish a connection between the complexity of the problem and its underlying structure: we prove that for k⩽3 the minimum number of necessary recolourings is polynomial in the size of the graph, while for k⩾4 instances exist where this number is superpolynomial.

Citation

Bonsma, P., Cereceda, L., van den Heuvel, J., & Johnson, M. (2007). Finding Paths between Graph Colourings: Computational Complexity and Possible Distances. Electronic Notes in Discrete Mathematics, 29, 463-469. https://doi.org/10.1016/j.endm.2007.07.073

Journal Article Type	Article
Publication Date	Aug 15, 2007
Deposit Date	Mar 17, 2014
Journal	Electronic Notes in Discrete Mathematics
Print ISSN	1571-0653
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	29
Pages	463-469
DOI	https://doi.org/10.1016/j.endm.2007.07.073
Keywords	Colour graph, PSPACE-completeness, Superpolynomial paths.