Cereceda, L. and van den Heuvel, J. and Johnson, M. (2008) 'Connectedness of the graph of vertex-colourings.', Discrete mathematics., 308 (5-6). pp. 913-919.
For a positive integer <i>k</i> and a graph <i>G</i>, the <i>k</i>-colour graph of <i>G</i> is the graph that has the proper <i>k</i>-vertex-colourings of G as its vertex set, and two <i>k</i>-colourings are joined by an edge in the <i>k</i>-colour graph if they differ in colour on just one vertex of <i>G</i>. In this note some results on the connectivity of the <i>k</i>-colour graph are proved. In particular it is shown that if <i>G</i> has chromatic number <i>k</i>=2 or 3, then the <i>k</i>-colour graph is not connected. On the other hand, for <i>k</i>>3 there are graphs with chromatic number <i>k</i> for which the <i>k</i>-colour graph is not connected, and there are <i>k</i>-chromatic graphs for which the <i>k</i>-colour graph is connected.
|Keywords:||Vertex colouring, k-colour graph, Glauber dynamics.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.disc.2007.07.028|
|Record Created:||07 Oct 2008|
|Last Modified:||01 Apr 2010 22:40|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|