**Reference**:- Takehiro Ito, Marcin Kamiński, and Erik D. Demaine, “Reconfiguration of List Edge-Colorings in a Graph”, in
*Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009)*, Lecture Notes in Computer Science, volume 5664, Banff, Alberta, Canada, August 21–23, 2009, pages 375–386. **Abstract**:-
We study the problem of reconfiguring one list edge-coloring of a graph into
another list edge-coloring by changing one edge color at a time, while at all
times maintaining a list edge-coloring, given a list of allowed colors for
each edge. First we show that this problem is PSPACE-complete, even for
planar graphs of maximum degree 3 and just six colors. Then we consider
the problem restricted to trees. We show that any list edge-coloring can be
transformed into any other under the sufficient condition that the number of
allowed colors for each edge is strictly larger than the degrees of both its
endpoints. This sufficient condition is best possible in some sense. Our
proof yields a polynomial-time algorithm that finds a transformation between
two given list edge-colorings of a tree with
*n*vertices using*O*(*n*^{2}) recolor steps. This worst-case bound is tight: we give an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(*n*^{2}) recolor steps. **Comments**:- This paper is also available from SpringerLink.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (2628k), gzipped PostScript (1217k), and PDF (164k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- NPReconfiguration_DAM2012 (Reconfiguration of List Edge-Colorings in a Graph)
- NPReconfiguration_TCS (On the Complexity of Reconfiguration Problems)
- SubsetSumReconfiguration_JOCO (Approximability of the Subset Sum Reconfiguration Problem)
- NPReconfiguration_ISAAC2008 (On the Complexity of Reconfiguration Problems)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.