Hoa Vu: Toward the Locality of Vizing's Theorem

Abstract: 
Vizing showed that it suffices to color the edges of a simple graph using $\Delta + 1$ colors, where $\Delta$ is the maximum degree of a graph. However, up to this date, no efficient distributed edge-coloring algorithms are known for obtaining such a coloring. The algorithms that are closest to this number of colors are the randomized $(\Delta + \tilde{\Theta}(\sqrt{\Delta}))$-edge-coloring algorithm that runs in polylog(n) rounds by Chang et al. (SODA '18) and the deterministic $(\Delta + polylog(n))$-edge-coloring algorithm that runs in $\poly(\Delta, log n)$ by Ghaffari et al. (STOC'18).

We present a randomized distributed edge-coloring algorithm that uses $\Delta + 2$ colors and runs in $\poly(\Delta, log n)$ rounds. 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 $\Delta + 2\ell - 1$ colors. We show how to achieve $\ell = 1$ with randomization and $\ell = O(\log n / \log \log n)$ without randomization. The former leads to our $(\Delta + 2)$-edge-coloring algorithm while the latter leads to a $\poly(\Delta, log n)$-rounds deterministic ($\Delta + O(\log n / \log \log n )$)-edge-coloring algorithm.

This is a joint work with Hsin-Hao Su.