Distributed Graph Coloring and Other Symmetry Breaking Problems

Graphs, Hypergraphs, and Computing

20 February 15:30 - 16:30

Michael Elkin - Ben Gurion University of the Negev

Consider an unweighted undirected graph G, and suppose that each vertex hosts a processor. The processors communicate over edges of G. Suppose also that the communication is synchronous, i.e., it proceeds in discrete rounds. On each round each vertex is allowed to send messages to all its neighbors. How many rounds are needed to color the graph G legally in (Delta+1) colors, where Delta is the maximum degree of the graph G? How many rounds are needed to compute a maximal (under containment) independent set, or a maximal matching?

These are classical questions in distributed computing. Efficient randomized algorithms for these problems were devised more than twenty years ago. On the other hand, efficient deterministic algorithms turned out to be far more elusive. Recently significant progress was achieved in devising such algorithms, but still many central questions remain wide open. Major progress was also achieved in devising randomized algorithms.

In this talk I will survey this area, discuss recent results and main open problems.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to