Fast and Simple Edge-Coloring Algorithms
Christiansen, Aleksander B. G., Rotenberg, Eva, Vlieghe, Juliette · arXiv (Cornell University) · 2019
In 1965, Vizing [Vadim G. Vizing, 1965] showed that every planar graph of maximum degree Δ ≥ 8 can be edge-colored using Δ colors. The direct implementation of Vizing’s proof gives an algorithm that finds the coloring in O(n²) time for an n-vertex input graph. Chrobak and Nishizeki [Marek Chrobak and Takao Nishizeki, 1990] have shown a more careful algorithm, which improves the time to O(nlog n), though only for Δ ≥ 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 of maximum degree 8 in the sense that in time O(nlog n) the algorithm colors the graph using the optimal number of colors which may be 9 for relatively small graphs.