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

Vizing's theorem states that any n-vertex m-edge graph of maximum degree Δ can be { edge colored} using at most Δ + 1 different colors [Diskret.~Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in Õ(mn) time. This was subsequently improved to O(m√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 O(mn1/3) time, giving the first polynomial improvement for this fundamental problem in over 40 years.