Reconfiguration graph for vertex colourings of weakly chordal graphs

Abstract

We show that for each k>=3 there is a k-colourable weakly chordal graph G such that the reconfiguration graph R_k+1(G) is disconnected. We also introduce a subclass of k-colourable weakly chordal graphs and show that their reconfiguration graphs have quadratic diameter.

Keywords

• graph coloring
• reconfiguration graph
• chordal graphs