We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Finding paths between graph colourings : computational complexity and possible distances.

Bonsma, Paul and Cereceda, Luis and van den Heuvel, Jan and Johnson, Matthew (2007) 'Finding paths between graph colourings : computational complexity and possible distances.', Electronic notes in discrete mathematics., 29 . pp. 463-469.


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.

Item Type:Article
Keywords:Colour graph, PSPACE-completeness, Superpolynomial paths.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:August 2007
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar