Theory Seminar

Distributed Edge Coloring

Yi-Jun Chang

University of Michigan
Friday, April 13, 2018
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

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ཎ).

Additional Information

Sponsor(s): CSE

Open to: Public