论文标题
构建一个较大的图表，以有效地重新配置顶点着色
Building a larger class of graphs for efficient reconfiguration of vertex colouring
论文作者
论文摘要
图$ g $的$ k $彩色是$ g $的顶点的最多$ k $颜色的分配，因此相邻的顶点分配了不同的颜色。 $ K $ -Colourings的重新配置图，$ \ Mathcal {r} _K（g）$，是其顶点的图形，其顶点为$ g $的$ k $ - 颜色，两种颜色在$ \ Mathcal {r} _k（r} _k（g）$上，如果它们在恰好的颜色上有所不同。对于$ k $ - 颜色图$ g $，我们研究了$ \ Mathcal {r} _ {k+1}（g）$的连接性和直径。众所周知，并非所有弱和弦图都具有$ \ MATHCAL {r} _ {k+1}（g）$连接的属性。另一方面，连接了$ \ Mathcal {r} _ {k+1}（g）$，直径$ o（n^2）$的直径$ O（n^2）$，用于几个弱弦，弦，和弦，和弦双部分和$ p_4 $ free graphs等弱弦图。 我们介绍了一类称为燕麦图的新类图，该图形扩展了后者的类别，实际上扩展了弱弦图的类别。燕麦图是由四个简单操作，不相交联合，加入以及添加集团或可比顶点构建的。我们证明，如果$ g $是$ k $ - 颜色的燕麦图，则$ \ mathcal {r} _ {k+1}（g）$与直径$ o（n^2）$连接。此外，我们给出了多项式时间算法以识别燕麦图并在$ \ Mathcal {r} _ {k+1}（g）$中找到任何两种颜色之间的路径。
A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two colourings are joined by an edge in $\mathcal{R}_k(G)$ if they differ in colour on exactly one vertex. For a $k$-colourable graph $G$, we investigate the connectivity and diameter of $\mathcal{R}_{k+1}(G)$. It is known that not all weakly chordal graphs have the property that $\mathcal{R}_{k+1}(G)$ is connected. On the other hand, $\mathcal{R}_{k+1}(G)$ is connected and of diameter $O(n^2)$ for several subclasses of weakly chordal graphs such as chordal, chordal bipartite, and $P_4$-free graphs. We introduce a new class of graphs called OAT graphs that extends the latter classes and in fact extends outside the class of weakly chordal graphs. OAT graphs are built from four simple operations, disjoint union, join, and the addition of a clique or comparable vertex. We prove that if $G$ is a $k$-colourable OAT graph then $\mathcal{R}_{k+1}(G)$ is connected with diameter $O(n^2)$. Furthermore, we give polynomial time algorithms to recognize OAT graphs and to find a path between any two colourings in $\mathcal{R}_{k+1}(G)$.
