Diameter of Colorings Under Kempe Changes

Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa

研究成果: Conference contribution

4 被引用数 (Scopus)


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 ≥, 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.

ホスト出版物のタイトルComputing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
編集者Ding-Zhu Du, Zhenhua Duan, Cong Tian
出版社Springer Verlag
出版ステータスPublished - 2019
イベント25th International Computing and Combinatorics Conference, COCOON 2019 - Xi'an, China
継続期間: 2019 7月 292019 7月 31


名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
11653 LNCS


Conference25th International Computing and Combinatorics Conference, COCOON 2019

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)


「Diameter of Colorings Under Kempe Changes」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。