For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Coloring Reconfiguration Problem on Specific Graph Classes
Tatsuhiko HATANAKA Takehiro ITO Xiao ZHOU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
chordal graphs, combinatorial reconfiguration, graph algorithm, graph coloring, PSPACE-complete,
Full Text: PDF>>
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.