The Coloring Reconfiguration Problem on Specific Graph Classes

Tatsuhiko HATANAKA  Takehiro ITO  Xiao ZHOU  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.423-429
Publication Date: 2019/03/01
Publicized: 2018/10/30
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0005
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
chordal graphs,  combinatorial reconfiguration,  graph algorithm,  graph coloring,  PSPACE-complete,  

Full Text: PDF>>
Buy this Article



Summary: 
We study the problem of transforming one (vertex) c-coloring 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.