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

Anton Bernshteyn, Abhishek Dhawan

We present a randomized algorithm that, given a constant $\epsilon >0$, outputs a proper $(1+\epsilon )\Delta$-edge-coloring of an $m$-edge simple graph $G$ of maximum degree $\Delta \ge 1/\epsilon$ in $O(m)$ tim…