Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1587/transinf.2018FCP0005 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
chordal graphs, combinatorial reconfiguration, graph algorithm, graph coloring, PSPACE-complete | Edge coloring,Complete coloring,Discrete mathematics,Combinatorics,Comparability graph,Computer science,Bipartite graph,Chordal graph,List coloring,Distance-hereditary graph,Graph coloring | Conference |
Volume | Issue | ISSN |
E102D | 3 | 1745-1361 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tatsuhiko Hatanaka | 1 | 0 | 0.68 |
| Takehiro Ito | 2 | 260 | 40.71 |
| Xiao Zhou | 3 | 325 | 43.69 |