List edge multicoloring in bounded cyclicity graphs
Dániel Marx · 2003
The list edge multicoloring problem is a version of edge coloring where every edge e has a list of available colors L(e) and an integer demand x(e). For each e, we have to select x(e) colors from L(e) such that adjacent edges receive disjoint sets of colors. Marcotte and Seymour proved a good characterization theorem for list edge multicoloring in trees, which can be turned into a polynomial time algorithm.