Reconfiguration Graphs for Vertex Colorings of P5-Free Graphs  

作　　者：Hui Lei Yulai Ma Zhengke Miao Yongtang Shi Susu Wang 

机构地区：[1]School of Statistics and Data Science,LPMC and KLMDASR,Nankai University,Tianjin 300071,China [2]Department of Mathematics,Paderborn University,Warburger Str.100,Paderborn 33098,Germany [3]School of Mathematics and Statistics&Key Laboratory of Analytical Mathematics and Applications(Ministry of Education),Fujian Normal University,Fuzhou,Fujian 350007,China [4]Center for Combinatorics and LPMC,Nankai University,Tianjin 300071,China

出　　处：《Annals of Applied Mathematics》2024年第4期393-410,共18页应用数学年刊(英文版)

基　　金：supported by the National Natural Science Foundation of China(Nos.12371351 and 12431013);supported by the National Natural Science Foundation of China(Nos.12031018 and 12431013);the Young Elite Scientist Sponsorship Program by CAST;the Fundamental Research Funds for the Central Universities,Nankai University。

摘　　要：For any positive integer k,the reconfiguration graph for all k-colorings of a graph G,denoted by 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,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 R_(8p)(G)is disconnected.In this paper,we offer a detailed classification of the connectivity of R_(k)(G)conc(erning t-chromatic P_(5)-free graphs G for cases t=3,and t≥4 with k≤(^(t)2).We demonstrate that R_(k)(G)remains connected for each 3-chromatic P_(5)-free graph G and each k≥4.Furthermore,for each t≥4 and k≤(^(t)2).we provide a construction of a t-chromatic P_(5)-free graph G with R_(k)(G)being disconnected.This resolves a question posed by Feghali and Merkel.

关 键 词：Reconfiguration graphs Ps-free graphs frozen colorings k-mixing 

分 类 号：O157.5[理学—数学]