@article { ,
title = {Mixing 3-colourings in bipartite graphs},
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.},
doi = {10.1016/j.ejc.2009.03.011},
issn = {0195-6698},
issue = {7},
journal = {European Journal of Combinatorics},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {1593-1606},
publicationstatus = {Published},
publisher = {Elsevier},
volume = {30},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2009},
author = {Cereceda, Luis and van den Heuvel, Jan and Johnson, Matthew}
}