An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree

Takehiro ITO, Kazuto KAWAMURA, Xiao ZHOU

Summary :

We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kamiski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n²) recoloring steps. We remark that the upper bound O(n²) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n²) recoloring steps.

• Publication: IEICE TRANSACTIONS on Information Vol.E95-D No.3 pp.737-745
• Publication Date: 2012/03/01
• Online ISSN: 1745-1361
• DOI: 10.1587/transinf.E95.D.737
• Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)

Authors

Takehiro ITO
Kazuto KAWAMURA
Xiao ZHOU

Keyword

graph algorithm,  list edge-coloring,  reachability on solution space,  reconfiguration problem,  tree