Recoloring via modular decomposition
<|reference_start|>Recoloring via modular decomposition: The reconfiguration graph of the $k$-colorings of a graph $G$, denoted $R_{k}(G)$, is the graph whose vertices are the $k$-colorings of $G$ and two colorings are adjacent in $R_{k}(G)$ if they differ in color on exactly one vertex. A graph $G$ is said to be recolorable if $R_{\ell}(G)$ is connected for all $\ell \geq \chi(G)$+1. We use the modular decomposition of several graph classes to prove that the graphs in the class are recolorable. In particular, we prove that every ($P_5$, diamond)-free graph, every ($P_5$, house, bull)-free graph, and every ($P_5$, $C_5$, co-fork)-free graph is recolorable.<|reference_end|>
@article{belavadi2024recoloring,
    title={Recoloring via modular decomposition},
    author={Manoj Belavadi, Kathie Cameron and Ni Luh Dewi Sintiari},
    journal={arXiv preprint arXiv:2405.06446},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.06446},
    primaryClass={math.CO cs.DM}
}