TY - GEN
T1 - Reconfiguration of list edge-colorings in a graph
AU - Ito, Takehiro
AU - Kamiński, Marcin
AU - Demaine, Erik D.
N1 - Funding Information:
The first author’s work was partially supported by Grant-in-Aid for Scientific Research 22700001 . The second author is Chargé de Recherches du F.R.S.–FNRS. He has also been partially supported by National Science Center grant number DEC-2011/02/A/ST6/00201 .
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=69949157763&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69949157763&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03367-4_33
DO - 10.1007/978-3-642-03367-4_33
M3 - Conference contribution
AN - SCOPUS:69949157763
SN - 3642033660
SN - 9783642033667
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 375
EP - 386
BT - Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
T2 - 11th International Symposium on Algorithms and Data Structures, WADS 2009
Y2 - 21 August 2009 through 23 August 2009
ER -