A linear-time algorithm for $(1+\epsilon )\mathrm{\Delta }$-edge-coloring

We present a randomized algorithm that, given a constant $\epsilon >0$, outputs a proper $(1+\epsilon )\mathrm{\Delta }$-edge-coloring of an $m$-edge simple graph $G$ of maximum degree $\mathrm{\Delta }\ge 1\mathrm{/}\epsilon$ in $O(m)$ time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of $\mathrm{\Delta }$. Indeed, even for edge-coloring with $2\mathrm{\Delta }-1$ colors (i.e., meeting the “greedy” bound), no such linear-time algorithm has been previously known.