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

Sayan Bhattacharya, Din Carmon, Martín Costa +2

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 or…