Cookies

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 (2009) 'Mixing 3-colourings in bipartite graphs.', European journal of combinatorics., 30 (7). pp. 1593-1606.

Abstract

For a 3-colourable graph G, the 3-colour graph of G, denoted 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 one decide whether or not 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 View the MathML source 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:Article
Full text:PDF - Accepted Version (384Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.ejc.2009.03.011
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in European journal of combinatorics.
Record Created:01 Oct 2010 14:50
Last Modified:29 Oct 2010 12:51

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