Diameter of colorings under Kempe changes
Diameter of colorings under Kempe changes
复制标题
Kempe 下着色直径的变化
DOI：
10.1016/j.tcs.2020.05.033
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Wasa Kunihiro
中科院分区：
文献类型：
--
作者：
Bonamy Marthe;Heinrich Marc;Ito Takehiro;Kobayashi Yusuke;Mizuta Haruka;Muehlenthaler Moritz;Suzuki Akira;Wasa Kunihiro
给定图G的一个k-染色，对两个颜色a和B的肯普变换产生G的另一个k-染色，如下：首先在G的子图中选择一个由两个颜色类a和B诱导的连通分支，然后交换该分支中的颜色a和B。两个k-着色称为肯普等价的，如果一个可以通过肯普变换序列转化为另一个。我们考虑两个问题，定义如下：第一，给定图G的两个k-着色，Kempe可达性询问它们是否是Kempe等价的;第二，给定图G和正整数k，Kempe连通性询问G的任何两个k-着色是否是Kempe等价的。我们分析了这些问题的复杂性，从图类的观点。我们证明了Kempe可达性是PSPACE-完全的，对于任意固定的k≥ 3，并且即使限制为三色和最大度为6的平面图，它也是PSPACE-完全的。此外，我们还证明了这两个问题都允许弦图、二部图和上图上的多项式时间算法。对于这些图类中的每一个，我们给出了一个非平凡的上界的数量Kempe的变化，以证明两个k-着色是Kempe等价的。
Given a k-coloring of a graph G, a Kempe-change for two colors a and b produces another k-coloring of G, as follows: first choose a connected component in the subgraph of G induced by the two color classes of a and b, and then swap the colors a and b in the component. Two k-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two k-colorings of a graph G, Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph G and a positive integer k, Kempe Connectivity asks whether any two k-colorings of G are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is PSPACE-complete for any fixed k≥ 3, and that it remains PSPACE-complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two k-colorings are Kempe-equivalent.