Distributed Edge Coloring

In this talk we discuss distributed edge coloring algorithms using small number of colors. Vizing's theorem says that every graph can be Â^†-edge colored. However, it is still open whether such a coloring can be constructed locally (i.e., each edge e chooses its color only based on information within its distance-t neighborhood, where t = poly(Â^†, log n)). It is well-known that a (2Â^† Â^’ 1)-edge coloring can be constructed locally (e.g., iterative packing of maximal matching, for 2Â^† Â^’ 1 times). Going below the natural barrier of 2Â^† Â^’ 1 colors is quite a challenge. In this talk I will show present a distributed algorithm that uses (1+o(1))Â^† colors.

The talk is mainly based on https://arxiv.org/abs/1711.05469 (STOC'18).