Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier

Vizing's theorem states that any n-vertex m-edge graph of maximum degree$\Delta$can be edge colored using at most$\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}(mn^{1/3})$, time, giving the first polynomial improvement for this fundamental problem in over 40 years.