Vizing's Theorem in Near-Linear Time

Vizing's theorem states that any n-vertex m-edge graph of maximum degree ∆ can be edge colored using at most ∆ + 1 different colors [Vizing, 1964]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m √ n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n 2 ) by [Assadi, 2024] and Õ(mn 1/3 ) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn 1/4 ) by [Bhattacharya, Costa, Solomon and Zhang, 2024]).

In this paper, we present a randomized algorithm that computes a (∆ + 1)-edge coloring in near-linear time-in fact, only O(m log ∆) time-with high probability, giving a near-optimal algorithm for this fundamental problem.