»ã±¨±êÌâ (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}.