The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
It closes the remaining gap for Δ=8 in the efficient implementation of Vizing's theorem for planar graphs, providing a complete O(n log n) solution for all Δ≥8.
This paper presents an O(n log n) algorithm for edge-coloring planar graphs with maximum degree Δ=8 using Δ colors, extending previous work that covered Δ≥9. The result also generalizes to bounded genus graphs.
In 1965, Vizing [Diskret. Analiz, 1965] showed that every planar graph of maximum degree $Δ\ge 8$ can be edge-colored using $Δ$ colors. The direct implementation of the Vizing's proof gives an algorithm that finds the coloring in $O(n^2)$ time for an $n$-vertex input graph. Chrobak and Nishizeki [J. Algorithms, 1990] have shown a more careful algorithm, which improves the time to $O(n\log n)$ time, though only for $Δ\ge 9$. In this paper, we extend their ideas to get an algorithm also for the missing case $Δ=8$. To this end, we modify the original recoloring procedure of Vizing. This generalizes to bounded genus graphs.