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

Takehiro ITO  Kazuto KAWAMURA  Xiao ZHOU  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.3   pp.737-745
Publication Date: 2012/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.737
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
graph algorithm,  list edge-coloring,  reachability on solution space,  reconfiguration problem,  tree,  

Full Text: PDF(357.2KB)>>
Buy this Article




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(n2) recoloring steps. We remark that the upper bound O(n2) 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 Ω(n2) recoloring steps.