The coloring reconfiguration problem on specific graph classes

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)423-429
Number of pages7
JournalIEICE Transactions on Information and Systems
Issue number3
Publication statusPublished - 2019 Mar 1


  • Chordal graphs
  • Combinatorial reconfiguration
  • Graph algorithm
  • Graph coloring
  • PSPACE-complete


Dive into the research topics of 'The coloring reconfiguration problem on specific graph classes'. Together they form a unique fingerprint.

Cite this