@Article{AAM-40-394,
author = {Lei , HuiMa , YulaiMiao , ZhengkeShi , Yongtang and Wang , Susu},
title = {Reconfiguration Graphs for Vertex Colorings of $P_5$-Free Graphs},
journal = {Annals of Applied Mathematics},
year = {2025},
volume = {40},
number = {4},
pages = {394--411},
abstract = {<p style="text-align: justify; margin-top: 10px; margin-bottom: 5px;">For any positive integer $k,$ the reconfiguration graph for all $k$-colorings of a graph $G,$ denoted by $\mathcal{R}_k(G),$ is the graph where vertices represent
the $k$-colorings of $G,$ and two $k$-colorings are joined by an edge if they differ in
color on exactly one vertex. Bonamy et al. established that for any 2-chromatic $P_5$-free graph $G,$ $\mathcal{R}_k(G)$ is connected for each $k≥3.$ On the other hand, Feghali
and Merkel proved the existence of a $7p$-chromatic $P_5$-free graph $G$ for every
positive integer $p,$ such that $\mathcal{R}_{8p}(G)$ is disconnected.<br/><br/>In this paper, we offer a detailed classification of the connectivity of $\mathcal{R}_k(G)$ concerning $t$-chromatic $P_5$-free graphs $G$ for cases $t = 3,$ and $t ≥ 4$ with $t+1 ≤
k ≤\Bigg(\begin{matrix} t \\ 2 \end{matrix}\Bigg).$ We demonstrate that $\mathcal{R}_k(G)$ remains connected for each 3-chromatic $P_5$-free graph $G$ and each $k ≥4.$ Furthermore, for each $t≥4$ and $\Bigg(\begin{matrix} t \\ 2 \end{matrix}\Bigg),$&nbsp;we provide a construction of a $t$-chromatic $P_5$-free graph $G$ with $\mathcal{R}_k(G)$ being
disconnected. This resolves a question posed by Feghali and Merkel.</p>},
issn = {},
doi = {https://doi.org/10.4208/aam.OA-2024-0024},
url = {http://global-sci.org/intro/article_detail/aam/23777.html}
}