An asymptotic approximation scheme for multigraph edge coloring
with Peter Sanders. SODA 2005, ACM Trans. Algorithms 4, 2 (2008).
The edge coloring problem asks for assigning colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, i.e., parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. One of our algorithms achieves solution quality and has execution time polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.