TY - JOUR

T1 - The coloring reconfiguration problem on specific graph classes

AU - Hatanaka, Tatsuhiko

AU - Ito, Takehiro

AU - Zhou, Xiao

N1 - Funding Information:
Manuscript received March 20, 2018. Manuscript revised June 4, 2018. Manuscript publicized October 30, 2018. †The authors are with Graduate School of Information Sciences, Tohoku University, Sendai-shi, 980–8579 Japan. ∗A preliminary version of this paper has been presented at the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017) [11]. This work is partially supported by JST CREST Grant Number JPMJCR1402, and by JSPS KAKENHI Grant Numbers JP16J02175, JP16K00003, and JP16K00004, Japan. a) E-mail: hatanaka@ecei.tohoku.ac.jp b) E-mail: takehiro@ecei.tohoku.ac.jp c) E-mail: zhou@ecei.tohoku.ac.jp DOI: 10.1587/transinf.2018FCP0005
Publisher Copyright:
Copyright © 2019 The Institute of Electronics, Information and Communication Engineers.

PY - 2019/3/1

Y1 - 2019/3/1

N2 - We study the problem of transforming one (vertex) ccoloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.

AB - We study the problem of transforming one (vertex) ccoloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.

KW - Chordal graphs

KW - Combinatorial reconfiguration

KW - Graph algorithm

KW - Graph coloring

KW - PSPACE-complete

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

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

U2 - 10.1587/transinf.2018FCP0005

DO - 10.1587/transinf.2018FCP0005

M3 - Article

AN - SCOPUS:85063988572

SN - 0916-8532

VL - E102D

SP - 423

EP - 429

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 3

ER -