Abstract
A $k$-colouring of a graph $G=(V,E)$ is a mapping $c: V\rightarrow\{1,2,\ldots,k\}$ such that $c(u)\neq 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 \emph{$k$-colour-dense} graphs. We show that for each $k$-colour-dense graph $G$, the reconfiguration graph of the $\ell$-colourings of $G$ is connected and has diameter $O(|V|^2)$, for all $\ell\geq 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 \geq 2$ there is a $k$-colourable chordal graph~$G$ whose reconfiguration graph of the $(k+1)$-colourings has diameter $\Theta(|V|^2)$.