论文标题
颜色和统治集合中的重新配置：调查
Reconfiguration of Colourings and Dominating Sets in Graphs: a Survey
论文作者
论文摘要
我们调查了有关颜色和图表中的主导集的重新配置的结果。 $ k $颜色图$ \ mathcal {c} _ {k}（k}（g）$ g $的$对应于图形$ g $的适当$ k $ - 颜色，而两个$ k $ - 颜色在一个完全不同的颜色的颜色上都相邻。同样，$ k $ - edged色的图$ \ nathcal {ec} _ {k}（g）$ g $的$是$ g $的$ g $的适当$ k $ - edge-the，如果可以通过一个沿着expe-kempe，a chaine a a axim of a twos。边缘周期。 $ k $ dominating Graph $ \ Mathcal {d} _ {k}（g）$的顶点是（不一定是最小的）主导集合的$ g $ $ g $ $ k $或更低的集合，两个统治集均以$ \ \ mathcal {d} _ {d} _ {k}（g）添加到另一个范围内，或者是一个均可添加的频率，或者是一个均可添加的频率。另一方面，当我们将主导集限制为最小主导集时，例如，我们获得了不同类型的主导重新配置图，具体取决于是否沿边缘交换了顶点。 我们考虑着着色和统治重新配置图的这些类型的类型。猜想，问题和开放性问题在相关部分中说明。
We survey results concerning reconfigurations of colourings and dominating sets in graphs. The vertices of the $k$-colouring graph $\mathcal{C}_{k}(G)$ of a graph $G$ correspond to the proper $k$-colourings of a graph $G$, with two $k$-colourings being adjacent whenever they differ in the colour of exactly one vertex. Similarly, the vertices of the $k$-edge-colouring graph $\mathcal{EC}_{k}(G)$ of $g$ are the proper $k$-edge-colourings of $G$, where two $k$-edge-colourings are adjacent if one can be obtained from the other by switching two colours along an edge-Kempe chain, i.e., a maximal two-coloured alternating path or cycle of edges. The vertices of the $k$-dominating graph $\mathcal{D}_{k}(G)$ are the (not necessarily minimal) dominating sets of $G$ of cardinality $k$ or less, two dominating sets being adjacent in $\mathcal{D}_{k}(G)$ if one can be obtained from the other by adding or deleting one vertex. On the other hand, when we restrict the dominating sets to be minimum dominating sets, for example, we obtain different types of domination reconfiguration graphs, depending on whether vertices are exchanged along edges or not. We consider these and related types of colouring and domination reconfiguration graphs. Conjectures, questions and open problems are stated within the relevant sections.
