Vizing’s Theorem from 1964 states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ+1 different colors. Vizing’s original proof is algorithmic and implies that such an edge coloring can be found in O(mn) time. In this talk, I’ll present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time — in fact, only O(mlogΔ) time — with high probability.
Based on https://arxiv.org/abs/2410.05240