Towards the Locality of Vizing's Theorem

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 $(Δ+ \tildeΘ(\sqrtΔ))$-edge-coloring algorithm that runs in $\text{polylog}(n)$ rounds by Chang et al. (SODA '18) and the deterministic $(Δ+ \text{polylog}(n))$-edge-coloring algorithm that runs in $\text{poly}(Δ, \log n)$ rounds by Ghaffari et al. (STOC '18). We present two distributed edge-coloring algorithms that run in $\text{poly}(Δ,\log n)$ rounds. The first algorithm, with randomization, uses only $Δ+2$ colors. The second algorithm is a deterministic algorithm that uses $Δ+ O(\log n/ \log \log n)$ colors. Our approach is to reduce the distributed edge-coloring problem into an online, restricted version of balls-into-bins problem. If $\ell$ is the maximum load of the bins, our algorithm uses $Δ+ 2\ell - 1$ colors. We show how to achieve $\ell = 1$ with randomization and $\ell = O(\log n / \log \log n)$ without randomization.