Recolouring co-bipartite and weakly chordal graphs.
2021
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 $G$ graph where
$\mathcal{R}_{k+n}(G)$ is disconnected, answering an open question of Feghali
and Fiala. We also show that for every $k$-colourable co-bipartite graph $G$,
$\mathcal{R}_{k+1}(G)$ is connected with diameter at most $4|V(G)|$.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
4
References
1
Citations
NaN
KQI