论文标题
顶点着色和禁止诱导子图的重新配置
Reconfiguration of vertex colouring and forbidden induced subgraphs
论文作者
论文摘要
$ k $ - 颜色的重新配置图，表示为$ \ Mathcal {r} _k（g）$，是该图，其顶点是$ g $的$ k $ - 颜色，两种颜色在$ $ \ nathcal {r} _k（r} _k（g）$中，如果它们在一个vertex上有差异。在本文中，我们调查了$ \ Mathcal {r} _ {k+1}（g）$的连接性和直径，以$ k $ - 颜色的图形$ g $限制为禁止诱导的子格言。我们表明，$ \ MATHCAL {r} _ {k+1}（g）$都可以为每一个$ k $ -olourable $ h $ h $ -free Graph $ g $时连接，并且仅当$ h $是诱导的$ p_4 $或$ p_3+p_3+p_1 $的诱导子级。我们还开始研究此问题，以针对由两个禁止诱导的子图定义的图形类别。我们表明，如果$ g $是$ k $ -olourable（$ 2k_2 $，$ c_4 $） - 免费图形，则$ \ Mathcal {r} _ {k+1}（g）$以直径为单位以$ 4N $连接。此外，我们证明$ \ MATHCAL {r} _ {k+1}（g）$是为每个$ k $ -colourable（$ p_5 $，$ c_4 $）连接的 - 免费图形$ g $。
The reconfiguration graph of the $k$-colourings, denoted $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two colourings are adjacent in $\mathcal{R}_k(G)$ if they differ in colour on exactly one vertex. In this paper, we investigate the connectivity and diameter of $\mathcal{R}_{k+1}(G)$ for a $k$-colourable graph $G$ restricted by forbidden induced subgraphs. We show that $\mathcal{R}_{k+1}(G)$ is connected for every $k$-colourable $H$-free graph $G$ if and only if $H$ is an induced subgraph of $P_4$ or $P_3+P_1$. We also start an investigation into this problem for classes of graphs defined by two forbidden induced subgraphs. We show that if $G$ is a $k$-colourable ($2K_2$, $C_4$)-free graph, then $\mathcal{R}_{k+1}(G)$ is connected with diameter at most $4n$. Furthermore, we show that $\mathcal{R}_{k+1}(G)$ is connected for every $k$-colourable ($P_5$, $C_4$)-free graph $G$.
