Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200608July 2006 
Mixing 3colourings in Bipartite Graphs
Luis Cereceda, Jan van den Heuvel and Matthew Johnson
For a 3colourable graph G, the 3colour graph of G, denoted C_{3}(G), is the graph with node set the proper vertex 3colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question: given G, how easily can we decide whether or not C_{3}(G) is connected? We show that the 3colour graph of a 3chromatic graph is never connected, and characterise the bipartite graphs for which C_{3}(G) is connected. We also show that the problem of deciding the connectedness of the 3colour graph of a bipartite graph is in the complexity class coNP, and that restricted to planar bipartite graphs, the question is answerable in polynomial time.This report is obsolete. The newer version CDAM Research Report LSECDAM200706 should be considered instead.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200608, 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 7494. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 