A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time

We present a simple $(1+\epsilon )\mathrm{\Delta }$-edge-coloring algorithm for graphs of maximum degree $\mathrm{\Delta }=\mathrm{\Omega }(\log n\mathrm{/}\epsilon )$ with running time $O\left(m{\log }^{3}n\mathrm{/}{\epsilon }^3\right)$. Our algorithm improves upon that of [Duan, He, and Zhang; SODA19], which was the first near-linear time algorithm for this problem. While our results are weaker than the current state-of-the-art, our approach is significantly simpler, both in terms of analysis as well as implementation, and may be of practical interest.