|
| Reconfiguration Graphs for VertexColorings of P5-Free Graphs |
| Hui Lei,Yulai Ma,Zhengke Miao,Yongtang Shi,Susu Wang |
| (School of Statistics and Data Science, LPMC and KLMDASR, Nankai
University, Tianjin 300071, China;Department of Mathematics, Paderborn University, Warburger Str. 100,
Paderborn 33098, Germany;School of Mathematics and Statistics & Key Laboratory of Analytical
Mathematics and Applications (Ministry of Education), Fujian Normal
University, Fuzhou, Fujian 350007, China;Center for Combinatorics and LPMC, Nankai University, Tianjin 300071,
China) |
| DOI： |
| Abstract: |
| For any positive integer k, the reconfiguration graph for all kcolorings of a graph G, denoted by Rk(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
P5-free graph G, Rk(G) is connected for each k≥3. On the other hand, Feghali
and Merkel proved the existence of a 7p-chromatic P5-free graph G for every
positive integer p, such that R8p(G) is disconnected.
In this paper, we offer a detailed classification of the connectivity of Rk(G)
concerning t-chromatic P5-free graphs G for cases t = 3, and t ≥ 4 with t+1 ≤
k ≤
We demonstrate that Rk(G) remains connected for each 3-chromatic
P5-free graph G and each k ≥4. Furthermore, for each t≥4 and t+1≤k ≤
we provide a construction of a t-chromatic P5-free graph G with Rk(G) being
disconnected. This resolves a question posed by Feghali and Merkel. |
| Key words: Reconfiguration graphs, P5-free graphs, frozen colorings, k-mixing. |