Faster Vizing and Near-Vizing Edge Coloring Algorithms

Vizing's celebrated theorem states that every simple graph with maximum degree Δ admits a (Δ+1) edge coloring which can be found in O(m · n) time on n-vertex m-edge graphs. This is just one color more than the trivial lower bound of Δ colors needed in any proper edge coloring. After a series of simplifications and variations, this running time was eventually improved by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to O(m√nlogn) time. This has effectively remained the state-of-the-art modulo an O(√logn)-factor improvement by Sinnamon in 2019. As our main result, we present a novel randomized algorithm that computes a Δ+O(logn) coloring of any given simple graph in O(mlogΔ) expected time; in other words, a near-linear time randomized algorithm for a ``near''-Vizing's coloring. As a corollary of this algorithm, we also obtain the following results: * A randomized algorithm for (Δ+1) edge coloring in O(n²logn) expected time. This is near-linear in the input size for dense graphs and presents the first polynomial time improvement over the longstanding bounds of Gabow et.al. for Vizing's theorem in almost four decades. * A randomized algorithm for (1+ε) Δ edge coloring in O(mlog(1/ε)) expected time for any ε = ω(logn/Δ). The dependence on ε exponentially improves upon a series of recent results that obtain algorithms with runtime of Ω(m/ε) for this problem.