Name
Abstract | ||
|---|---|---|
Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f(0) and f(r) of G, and asked whether there exists a sequence of list edge-colorings of G between f(0) and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer k >= 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer k >= 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if k <= 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: for every integer k >= 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1587/transfun.E101.A.232 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | DocType | Volume |
combinatorial reconfiguration, edge-coloring, planar graph, PSPACE-complete | Journal | E101A |
Issue | ISSN | Citations |
1 | 1745-1337 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiroki Osawa | 1 | 0 | 0.34 |
| Akira Suzuki | 2 | 51 | 8.44 |
| Takehiro Ito | 3 | 260 | 40.71 |
| Xiao Zhou | 4 | 325 | 43.69 |