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 (mnn) time. This has effectively remained the state-of-the-art modulo an O (n) -factor improvement by Sinnamon in 2019. As our main result, we present a novel randomized algorithm that computes a +O (n) coloring of any given simple graph in O (m) 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²n) 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 (m (1/) ) expected time for any = (n/). The dependence on exponentially improves upon a series of recent results that obtain algorithms with runtime of (m/) for this problem.