Resource title

Mixing 3-colourings in bipartite graphs

Resource image

image for OpenScout resource :: Mixing 3-colourings in bipartite graphs

Resource description

For a 3-colourable graph G, the 3-colour graph of G, denoted C3(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 C3(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 C3(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.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/6781/

Resource license