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 \(\tilde{O}(m\sqrt {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 \(\tilde{O}(n^2) \) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3}) \) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(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 .