Centre for Discrete and Applicable Mathematics

CDAM Research Report, LSE-CDAM-2007-06

February 2007

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 coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time.

A PDF file (258 kB) with the full contents of this report can be downloaded by clicking here.

(This paper supersedes the earlier paper Mixing 3-colourings in Bipartite Graphs, which is obsolete.)

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-06, 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