We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.

Bonamy, M. and Johnson, M. and Lignos, I. and Patel, V. and Paulusma, Daniel (2014) 'Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.', Journal of combinatorial optimization., 27 (1). pp. 132-143.


A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call k-colour-dense graphs. We show that for each k-colour-dense graph G, the reconfiguration graph of the ℓ-colourings of G is connected and has diameter O(|V|2), for all ℓ≥k+1. We show that this graph class contains the k-colourable chordal graphs and that it contains all chordal bipartite graphs when k=2. Moreover, we prove that for each k≥2 there is a k-colourable chordal graph G whose reconfiguration graph of the (k+1)-colourings has diameter Θ(|V|2).

Item Type:Article
Keywords:Reconfigurations, Graph colouring, Graph diameter, Chordal graphs.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:19 April 2013
Date of first online publication:January 2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar