An asymptotic approximation scheme for multigraph edge coloring

with Peter Sanders. SODA 2005, ACM Trans. Algorithms 4, 2 (2008).

PDF

Awarded with the Günter-Hotz Medal 2006, Invited to SODA 2005 special issue

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. One of our algorithms achieves solution quality $\mathrm{opt}+\sqrt{9\mathrm{opt}/2}$ and has execution time polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.