Fast and Simple $(1+\epsilon )\mathrm{\Delta }$-Edge-Coloring of Dense Graphs

Let $\epsilon \in (0,1)$ and $n,\mathrm{\Delta }\in \mathbb{N}$ be such that $\mathrm{\Delta }=\mathrm{\Omega }(\max \{\frac{\log n}{\epsilon },{(\frac{1}{\epsilon }\log \frac{1}{\epsilon })}^2\})$. Given an $n$-vertex $m$-edge simple graph $G$ of maximum degree $\mathrm{\Delta }$, we present a randomized $O\left(m{\log }^3\mathrm{\Delta }\mathrm{/}{\epsilon }^2\right)$-time algorithm that computes a proper $(1+\epsilon )\mathrm{\Delta }$-edge-coloring of $G$ with high probability. This improves upon the best known results for a wide range of the parameters $\epsilon$, $n$, and $\mathrm{\Delta }$. 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.