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.
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.
|Full text:||PDF - Accepted Version (384Kb)|
|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:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|