Cereceda, L. and van den Heuvel, J. and Johnson, M. (2008) 'Connectedness of the graph of vertex-colourings.', Discrete mathematics., 308 (5-6). pp. 913-919.
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.
| Item Type: | Article |
|---|---|
| Keywords: | Vertex colouring, k-colour graph, Glauber dynamics. |
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (158Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1016/j.disc.2007.07.028 |
| Publisher statement: | © 2007 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Date accepted: | No date available |
| Date deposited: | 11 December 2015 |
| Date of first online publication: | March 2008 |
| Date first made open access: | 16 April 2021 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
