Faster Vizing and Near-Vizing Edge Coloring Algorithms

Vizing’s celebrated theorem states that every simple graph with maximum degree $\mathrm{\Delta }$ admits a $(\mathrm{\Delta }+1)$ edge coloring which can be found in $O(m\cdot n)$ time on $n$-vertex $m$-edge graphs. This is just one color more than the trivial lower bound of $\mathrm{\Delta }$ 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\sqrt{n\log n})$ time. This has effectively remained the state-of-the-art modulo an $O(\sqrt{\log n})$-factor improvement by Sinnamon in 2019. As our main result, we present a novel randomized algorithm that computes a $\mathrm{\Delta }+O(\log n)$ coloring of any given simple graph in $O(m\log \mathrm{\Delta })$ 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 $(\mathrm{\Delta }+1)$ edge coloring in $O(n^2\log 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+\epsilon )\mathrm{\Delta }$ edge coloring in $O(m\log (1\mathrm{/}\epsilon ))$ expected time for any $\epsilon =\omega (\log n\mathrm{/}\mathrm{\Delta })$. The dependence on $\epsilon$ exponentially improves upon a series of recent results that obtain algorithms with runtime of $\mathrm{\Omega }(m\mathrm{/}\epsilon )$ for this problem.