Lukasz Kowalik

collaborators

2 papers

cs.DS2025

The planar edge-coloring theorem of Vizing in $O (n lo g n)$ time

Patryk Jędrzejczak, Łukasz Kowalik

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

cs.DS2024

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time

Lukasz Kowalik

In this paper we show that every graph $G$ of bounded maximum average degree $mad (G)$ and with maximum degree $Δ$ can be edge-colored using the optimal number of $Δ$ colors i…

The planar edge-coloring theorem of Vizing in O(nlogn) time

Edge-coloring sparse graphs with Δ colors in quasilinear time

The planar edge-coloring theorem of Vizing in $O (n lo g n)$ time

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time