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 C₃(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 C₃(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 C₃(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.

		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