Connectedness of the graph of vertex-colourings

Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew

Abstract

For a positive integer k and a graph G, the k-colour graph of G , Ck(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k -colourings are joined by an edge in Ck(G) if they differ in colour on just one vertex of G . In this note some results on the connectedness of Ck(G) are proved. In particular, it is shown that if G has chromatic number k∈{2,3}, then Ck(G) is not connected. On the other hand, for k⩾4 there are graphs with chromatic number k for which Ck(G) is not connected, and there are k -chromatic graphs for which Ck(G) is connected.

Citation

Cereceda, L., van den Heuvel, J., & Johnson, M. (2008). Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(5-6), 913-919. https://doi.org/10.1016/j.disc.2007.07.028

• Journal Article Type: Article
• Publication Date: Mar 28, 2008
• Deposit Date: Oct 7, 2008
• Publicly Available Date: Dec 11, 2015
• Journal: Discrete mathematics.
• Print ISSN: 0012-365X
• Electronic ISSN: 2578-9252
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 308
• Issue: 5-6
• Pages: 913-919
• DOI: https://doi.org/10.1016/j.disc.2007.07.028
• Keywords: Vertex colouring, k-colour graph, Glauber dynamics.
• Public URL: https://durham-repository.worktribe.com/output/1588153