
Speaker: Noah Golowich, April 30, 2019
Title. Distributed Graph Coloring
Abstract.
In the problem of distributed graph coloring, processors
located at the vertices of a graph communicate by passing
messages over the edges of this graph in multiple rounds
according to a predetermined protocol. The goal of such a
protocol is for the processors to compute a proper
coloring of the graph, using only the local information
collected from the messages. Many exciting advances
pertaining to this question have been made in the last
few years, yet some fundamental questions remain open.
I will discuss some algorithms and lower bounds for
special cases of the distributed graph coloring problem,
as well as connections with topological methods for
lowerbounding the chromatic number of a graph.
