The complexity of changing colourings with bounded maximum degree
Let G be a graph, x, y epsilon V(G), and phi : V (G) -> [K] a k-colouring of G such that phi(x) = phi(y). If Delta(G) >= k + root k - 1 then the following question is NP-complete: Does there exist a k-colouring phi' of such that phi' (x) not equal phi (Y)? Conversely, if Delta(G) <= k +root k - 3 then the problem is polynomial time. (C) 2010 Elsevier B.V. All rights reserved.
combinatorial problems computational complexity graph algorithms