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 Arjomandi in 1982 and independently by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to time. This has effectively remained the state- of-the-art modulo an -factor improvement by Sinnamon in 2019.