Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs

Let $ε\in (0, 1)$ and $n, Δ\in \mathbb N$ be such that $Δ= Ω\left(\max\left\{\frac{\log n}ε,\, \left(\frac{1}ε\log \frac{1}ε\right)^2\right\}\right)$. Given an $n$-vertex $m$-edge simple graph $G$ of maximum degree $Δ$, we present a randomized $O\left(m\,\log^3 Δ\,/\,ε^2\right)$-time algorithm that computes a proper $(1+ε)Δ$-edge-coloring of $G$ with high probability. This improves upon the best known results for a wide range of the parameters $ε$, $n$, and $Δ$. Our approach combines a flagging strategy from earlier work of the author with a shifting procedure employed by Duan, He, and Zhang for dynamic edge-coloring. The resulting algorithm is simple to implement and may be of practical interest.