We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Mixing 3-colourings in bipartite graphs.

Cereceda, Luis. and van den Heuvel, Jan. and Johnson, Matthew. (2007) 'Mixing 3-colourings in bipartite graphs.', in Graph-theoretic concepts in computer science. Heidelberg: Springer, pp. 166-177. Lecture notes in computer science. (4769).


For a 3-colourable graph G, the 3-colour graph of G, denoted $\mathcal{C}_3(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 $\mathcal{C}_3(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 $\mathcal{C}_3(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.

Item Type:Book chapter
Additional Information:Revised papers of the 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007.
Full text:PDF - Accepted Version (263Kb)
Publisher Web site:
Publisher statement:The original publication is available at
Record Created:07 Oct 2009 11:35
Last Modified:25 Nov 2011 09:51

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library