The planar edge-coloring theorem of Vizing in $O(n\log n)$ time

Patryk Jędrzejczak, Łukasz Kowalik

In 1965, Vizing [Diskret. Analiz, 1965] showed that every planar graph of maximum degree $\Delta \ge 8$ can be edge-colored using $\Delta$ colors. The direct implementation of the Vizing's pr…