Faster $(\Delta +1)$-Edge Coloring: Breaking the $m\sqrt{n}$ Time Barrier

Abstract

Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta +1$ different colors [Diskret.~Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde{O}(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al.~[1985]. In this paper we present an algorithm that computes such an edge coloring in $\tilde{O}(m{n}^{1/3})$ time, giving the first polynomial improvement for this fundamental problem in over 40 years.

arXiv commentStarted to circulate in April 2024