Name
Title | ||
|---|---|---|
An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree |
Abstract | ||
|---|---|---|
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, Kamiński 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
2) recoloring steps. We remark that the upper bound O(n
2) 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
2) recoloring steps.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-20877-5_10 | IEICE Transactions |
Keywords | Field | DocType |
sufficient condition,infinite family,n vertex,edge color assignment,improved sufficient condition,list edgecoloring,upper bound o,list edge-colorings,new sufficient condition,polynomial-time algorithm,recoloring step,upper bound,satisfiability,edge coloring | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Constructive,Upper and lower bounds,Computer science,Control reconfiguration | Journal |
Volume | Issue | ISSN |
95-D | 3 | 0302-9743 |
Citations | PageRank | References |
4 | 0.44 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Kazuto Kawamura | 2 | 17 | 1.14 |
| Xiao Zhou | 3 | 325 | 43.69 |