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.
|Keywords:||Colour graph, PSPACE-completeness, Superpolynomial paths.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.endm.2007.07.073|
|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|