Online Edge Coloring is (Nearly) as Easy as Offline

Joakim Blikstad, Ola Svensson, Radu Vintan +1

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree $\Delta$ can be edge colored (offline) using no more than $\Delta +1$ colors (with $\Delta$ being a tri…