报告题目 (Title)：Recoloring P5-free graphs
中文题目：重新着色无P5图
报告人 (Speaker)：史永堂 教授（南开大学）
报告时间 (Time)：2024年4月10日 (周三) 9:30
报告地点 (Place)：腾讯会议463560158
邀请人(Inviter)：何卓衡
摘要：A k-coloring of a graph G=(V,E) is a mapping \phi: V\to \{1,2,\ldots,k\} such that \phi(u)\neq\phi(v) for any edge uv\in E(G). The reconfiguration graph for the k-colorings of $G$, denoted by \mathcal{R}_k(G), is the graph whose vertices are the k -colorings of $ G $ and two colorings are joined by an edge if they differ in color on exactly one vertex. Let k and \ell be two integers with \ell> k\geq2.
For any k-colorable P_4-free graph G, Bonamy and Bousquet proved that \mathcal{R}_{\ell}(G) is connected. On the other hand, they pointed out that, there is a k-colorable P_6-free graph G with \mathcal{R}_{\ell}(G) disconnected. This leaves the open case P_5-free graphs. Feghali and Merkel proved that, for every positive integer p, there exists a 7p-colorable P_5-free graph G such that \mathcal{R}_{8p}(G) is disconnected.
In this talk, we shall prove that, \mathcal{R}_{\ell}(G) is connected for each 3-colorable P_5-free graph G and each \ell\geq4. We also show that, there exists a k -colorable P_5-free graph G with \mathcal{R}_{\ell}(G) disconnected for each k\geq4 and k+1\leq\ell\leq\binom{k}{2}.