Recolouring weakly chordal graphs and the complement of triangle-free graphs

Abstract

For a graph $G$, the $k$-recolouring graph ${\mathcal{R}}_k(G)$ is the graph whose vertices are the $k$-colourings of $G$ and two colourings are joined by an edge if they differ in colour on exactly one vertex. We prove that for all $n\ge 1$, there exists a $k$-colourable weakly chordal graph $G$ where ${\mathcal{R}}_{k+n}(G)$ is disconnected, answering an open question of Feghali and Fiala. We also show that for every $k$-colourable $3K_1$-free graph $G$, ${\mathcal{R}}_{k+1}(G)$ is connected with diameter at most $4|V(G)|$.

6 pages, 2 figures