Distributed Deterministic Graph Coloring

Consider an undirected unweighted n-vertex graph G = (V,E). All vertices host processors, and the processors communicate with each other over edges of G in discrete rounds. The communication is synchronous, and all vertices wake up simultaneously. Vertices have unique identity numbers. In each round each vertex can send distinct messages to all its neighbors. The running time of an algorithm in this model is the number of rounds of distributed communication
in its worst-case execution.

In the coloring problem we aim to construct a legal f(Delta)-coloring of G, where Delta is the maximum degree of G, and f() is some function. This is a classical and fundamental problem in Distributed Computing. Recently a significant progress was achieved in the study of this problem. I will overview most recent results on distributed coloring, and main techniques that were used to achieve this results. Many questions are left open, and I will present and discuss them. The talk will be self-contained.

The talk is based on a series of papers with Leonid Barenboim that were presented at PODC'08, STOC'09, and PODC'10.