Item

Abstract

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. Our algorithms achieve arbitrarily good approximation factors at the cost of slightly larger additive term. In particular, for any $\epsilon>0$ we achieve a solution quality of $(1+\epsilon)\opt+\Oh{1/\epsilon}$. The execution times of one algorithm are independent of $\epsilon$ and polynomial in the number of nodes and the \emph{logarithm} of the maximum edge multiplicity.