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 \ (O (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 \ (O (n²) \) by Assadi, 2024 and \ (O (mn^1/3) \) by Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024 (and subsequently to \ (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.