Volume 40, Issue 4
Reconfiguration Graphs for Vertex Colorings of $P_5$-Free Graphs

Hui Lei, Yulai Ma, Zhengke Miao, Yongtang Shi & Susu Wang

Ann. Appl. Math., 40 (2024), pp. 394-411.

Published online: 2025-01

Export citation
  • Abstract

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.

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),$ 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.

  • AMS Subject Headings

05C15, 05C

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@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 = {

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.

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),$ 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.

}, issn = {}, doi = {https://doi.org/10.4208/aam.OA-2024-0024}, url = {http://global-sci.org/intro/article_detail/aam/23777.html} }
TY - JOUR T1 - Reconfiguration Graphs for Vertex Colorings of $P_5$-Free Graphs AU - Lei , Hui AU - Ma , Yulai AU - Miao , Zhengke AU - Shi , Yongtang AU - Wang , Susu JO - Annals of Applied Mathematics VL - 4 SP - 394 EP - 411 PY - 2025 DA - 2025/01 SN - 40 DO - http://doi.org/10.4208/aam.OA-2024-0024 UR - https://global-sci.org/intro/article_detail/aam/23777.html KW - Reconfiguration graphs, $P_5$-free graphs, frozen colorings, $k$-mixing. AB -

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.

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),$ 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.

Lei , HuiMa , YulaiMiao , ZhengkeShi , Yongtang and Wang , Susu. (2025). Reconfiguration Graphs for Vertex Colorings of $P_5$-Free Graphs. Annals of Applied Mathematics. 40 (4). 394-411. doi:10.4208/aam.OA-2024-0024
Copy to clipboard
The citation has been copied to your clipboard