
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Complexity of (List) EdgeColoring Reconfiguration Problem
Hiroki OSAWA Akira SUZUKI Takehiro ITO Xiao ZHOU
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.1
pp.232238 Publication Date: 2018/01/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.232
Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: combinatorial reconfiguration, edgecoloring, planar graph, PSPACEcomplete,
Full Text: PDF(1.2MB)>>
Summary:
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 edgecolorings f_{0} and f_{r} of G, and asked whether there exists a sequence of list edgecolorings of G between f_{0} and f_{r} such that each list edgecoloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACEcomplete for every integer k ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the nonlist 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 PSPACEcomplete 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 nonlist variant: for every integer k ≥ 5, the nonlist variant is PSPACEcomplete even for planar graphs of bandwidth quadratic in k and maximum degree k.

