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:||(AM) Accepted Manuscript|
Download PDF (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.|
|Date accepted:||No date available|
|Date deposited:||29 October 2010|
|Date of first online publication:||October 2009|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|