@article { ,
title = {Connectedness of the graph of vertex-colourings},
abstract = {For a positive integer k and a graph G, the k-colour graph of G , Ck(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k -colourings are joined by an edge in Ck(G) if they differ in colour on just one vertex of G . In this note some results on the connectedness of Ck(G) are proved. In particular, it is shown that if G has chromatic number k∈\{2,3\}, then Ck(G) is not connected. On the other hand, for k⩾4 there are graphs with chromatic number k for which Ck(G) is not connected, and there are k -chromatic graphs for which Ck(G) is connected.},
doi = {10.1016/j.disc.2007.07.028},
issn = {0012-365X},
issue = {5-6},
journal = {Discrete mathematics.},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {913-919},
publicationstatus = {Published},
publisher = {Elsevier},
volume = {308},
keyword = {Algorithms and Complexity in Durham (ACiD), Vertex colouring, k-colour graph, Glauber dynamics.},
year = {2008},
author = {Cereceda, Luis and van den Heuvel, Jan and Johnson, Matthew}
}