Faster $(\mathrm{\Delta }+1)$-Edge Coloring: Breaking the $m\sqrt{n}$ Time Barrier

Vizing’s theorem states that any $n$-vertex $m$-edge graph of maximum degree $\mathrm{\Delta }$ can be {\em edge colored} using at most $\mathrm{\Delta }+1$ different colors [Diskret.~Analiz, '64]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde{O}(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al.~[1985]. In this paper we present an algorithm that computes such an edge coloring in $\tilde{O}(m{n}^{1\mathrm{/}3})$ time, giving the first polynomial improvement for this fundamental problem in over 40 years.