Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2006-08

July 2006

Mixing 3-colourings in Bipartite Graphs

Luis Cereceda, Jan van den Heuvel and Matthew Johnson

For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings 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 C3(G) is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which C3(G) is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is in the complexity class co-NP, and that restricted to planar bipartite graphs, the question is answerable in polynomial time.

This report is obsolete. The newer version CDAM Research Report LSE-CDAM-2007-06 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, LSE-CDAM-2006-08, 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)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk 

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2006