Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
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 graphG whose reconfiguration graph of the (k+1)-colourings has diameter ?(|V|2).
reconfigurations chordal graphs graph colouring graph diameter