Towards the Locality of Vizing's Theorem
share
Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithms are known for obtaining such a coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ̃(√(Δ)))-edge-coloring algorithm that runs in polylog(n) rounds by Chang et al. (SODA '18) and the deterministic (Δ + polylog(n))-edge-coloring algorithm that runs in poly(Δ, n) rounds by Ghaffari et al. (STOC '18). We present two distributed edge-coloring algorithms that run in poly(Δ, n) rounds. The first algorithm, with randomization, uses only Δ+2 colors. The second algorithm is a deterministic algorithm that uses Δ+ O( n/ n) colors. Our approach is to reduce the distributed edge-coloring problem into an online, restricted version of balls-into-bins problem. If ℓ is the maximum load of the bins, our algorithm uses Δ + 2ℓ - 1 colors. We show how to achieve ℓ = 1 with randomization and ℓ = O( n / n) without randomization.
READ FULL TEXT