Name
Abstract | ||
|---|---|---|
We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1587/transfun.E98.A.1168 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | DocType | Volume |
graph algorithm, list coloring, pathwidth, PSPACE-complete, reachability on solution space, reconfiguration | Journal | E98A |
Issue | ISSN | Citations |
6 | 1745-1337 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tatsuhiko Hatanaka | 1 | 0 | 0.68 |
| Takehiro Ito | 2 | 260 | 40.71 |
| Xiao Zhou | 3 | 325 | 43.69 |