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).
