Vizing's Theorem in Deterministic Almost-Linear Time

Vizing’s theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be edge colored using at most $\Delta + 1$ different colors. Vizing’s original proof is easily translated into a deterministic $O(mn)$ time algorithm. This deterministic time bound was subsequently improved to $\tilde{O}(m\sqrt{n})$ time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].