Abstract
The reconfiguration graph R-k(G) of the k-colourings of a graph 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. Bonamy et al. (2014) have shown that if G is a k-colourable chordal graph on n vertices, then Rk+1 (G) has diameter O(n(2)), and asked whether the same statement holds for k-colourable perfect graphs.
This was answered negatively by Bonamy and Bousquet (2014). In this note, we address this question for k-colourable weakly chordal graphs, a well-known class of graphs that falls between chordal graphs and perfect graphs.
We show that for each k >= 3 there is a k-colourable weakly chordal graph G such that Rk+1(G) is disconnected. On the positive side, we introduce a subclass of k-colourable weakly chordal graphs which we call k-colourable compact graphs and show that for each k-colourable compact graph G on n vertices, Rk+1(G) has diameter O(n(2)).
We show that this class contains all k-colourable co-chordal graphs and when k = 3 all 3-colourable (P-5, (P-5) over bar, C-5)-free graphs. We also mention some open problems. (C) 2019 Elsevier B.V.
All rights reserved.