Vizing's Theorem in Near-Linear Time

A textbook theorem by Vizing states that any graph with maximum degree \Delta admits an edge coloring which uses only (\Delta+ 1) different colors [Vizing, 1964]. In this talk, we will present the first algorithm that computes such a (\Delta+1)-edge coloring in near-linear time---in fact, only O(m log \Delta) time---with high probability. This gives the first near-optimal algorithm for this fundamental problem.

Joint work with Sepehr Assadi, Soheil Behnezhad, Martin Costa, Shay Solomon and Tinayi Zhang.