TY - JOUR

T1 - Diameter of colorings under Kempe changes

AU - Bonamy, Marthe

AU - Heinrich, Marc

AU - Ito, Takehiro

AU - Kobayashi, Yusuke

AU - Mizuta, Haruka

AU - Mühlenthaler, Moritz

AU - Suzuki, Akira

AU - Wasa, Kunihiro

N1 - Funding Information:
This work is partially supported by JSPS and MEAE-MESRI under the Japan-France Integrated Action Program (SAKURA). Bonamy and Heinrich are supported by the ANR Project GrR ( ANR-18-CE40-0032 ) operated by the French National Research Agency (ANR). Ito is partially supported by JSPS KAKENHI Grant Numbers JP19K11814 and JP18H04091 , and JST CREST Grant Number JPMJCR1402 , Japan. Kobayashi is partially supported by JSPS KAKENHI Grant Numbers JP16K16010 , JP16H03118 , JP17K19960 , and JP18H05291 , Japan. Mizuta is partially supported by JSPS KAKENHI Grant Number JP19J10042 , Japan. Suzuki is partially supported by JSPS KAKENHI Grant Numbers JP17K12636 and JP18H04091 , and JST CREST Grant Number JPMJCR1402 , Japan. Wasa is partially supported by JSPS KAKENHI Grant Number JP19K20350 and JST CREST Grant Numbers JPMJCR1401 and JPMJCR18K3 , Japan.
Funding Information:
This work is partially supported by JSPS and MEAE-MESRI under the Japan-France Integrated Action Program (SAKURA). Bonamy and Heinrich are supported by the ANR Project GrR (ANR-18-CE40-0032) operated by the French National Research Agency (ANR). Ito is partially supported by JSPS KAKENHI Grant Numbers JP19K11814 and JP18H04091, and JST CREST Grant Number JPMJCR1402, Japan. Kobayashi is partially supported by JSPS KAKENHI Grant Numbers JP16K16010, JP16H03118, JP17K19960, and JP18H05291, Japan. Mizuta is partially supported by JSPS KAKENHI Grant Number JP19J10042, Japan. Suzuki is partially supported by JSPS KAKENHI Grant Numbers JP17K12636 and JP18H04091, and JST CREST Grant Number JPMJCR1402, Japan. Wasa is partially supported by JSPS KAKENHI Grant Number JP19K20350 and JST CREST Grant Numbers JPMJCR1401 and JPMJCR18K3, Japan.
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2020/10/24

Y1 - 2020/10/24

N2 - 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.

AB - 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.

KW - Combinatorial reconfiguration

KW - Gaph coloring

KW - Graph algorithms

KW - Kempe equivalence

UR - http://www.scopus.com/inward/record.url?scp=85086135132&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086135132&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.05.033

DO - 10.1016/j.tcs.2020.05.033

M3 - Article

AN - SCOPUS:85086135132

SN - 0304-3975

VL - 838

SP - 45

EP - 57

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -