Fast algorithms for Vizing's theorem on bounded degree graphs
share
Vizing's theorem states that every graph G of maximum degree Δ can be properly edge-colored using Δ + 1 colors. The fastest currently known (Δ+1)-edge-coloring algorithm for general graphs is due to Sinnamon and runs in time O(m√(n)), where n = |V(G)| and m =|E(G)|. Using the bound m ≤Δ n/2, the running time of Sinnamon's algorithm can be expressed as O(Δ n^3/2). In the regime when Δ is considerably smaller than n (for instance, when Δ is a constant), this can be improved, as Gabow, Nishizeki, Kariv, Leven, and Terada designed an algorithm with running time O(Δ m log n) = O(Δ^2 n log n). Here we give an algorithm whose running time is only linear in n (which is obviously best possible) and polynomial in Δ. We also develop new algorithms for (Δ+1)-edge-coloring in the 𝖫𝖮𝖢𝖠𝖫 model of distributed computation. Namely, we design a deterministic 𝖫𝖮𝖢𝖠𝖫 algorithm with running time 𝗉𝗈𝗅𝗒(Δ, loglog n) log^5 n and a randomized 𝖫𝖮𝖢𝖠𝖫 algorithm with running time 𝗉𝗈𝗅𝗒(Δ) log^2 n. The key new ingredient in our algorithms is a novel application of the entropy compression method.
READ FULL TEXT