{"ID":2897977,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04516","arxiv_id":"2507.04516","title":"The planar edge-coloring theorem of Vizing in $O(n\\log n)$ time","abstract":"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.","short_abstract":"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] h...","url_abs":"https://arxiv.org/abs/2507.04516","url_pdf":"https://arxiv.org/pdf/2507.04516v2","authors":"[\"Patryk Jędrzejczak\",\"Łukasz Kowalik\"]","published":"2025-07-06T19:49:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}