We study the problem of transforming one (vertex) k-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a k-coloring, where k denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant k ≥ 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 the number of colors is a fixed constant. We then demonstrate that, even when the number of colors is a part of input, the problem is solvable in polynomial time for several graph classes, such as split graphs and trivially perfect graphs.
展开▼
