Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200511July 2005 
Connectedness of the Graph of VertexColourings
Luis Cereceda, Jan van den Heuvel and Matthew Johnson
For a positive integer k and a graph G, the kcolour graph of G, Ck(G), is the graph that has the proper kvertexcolourings of G as its vertex set, and two kcolourings 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 connectivity of Ck(G) are proved. In particular it is shown that if G has chromatic number k 2 {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 kchromatic graphs for which Ck(G) is connected.
A PDF file (177 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200511, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7732. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last modified: 5th August 2005