Distributed Graph Coloring
Ben-Gurion University of the Negev · Supervised by Prof. Michael Elkin
In a distributed graph, vertices coordinate their colors through local communication rounds such that adjacent vertices receive different colors. A standard goal is to use Δ + 1 colors, where Δ is the maximum degree of the graph. We instead focus on a number of colors that depends on the graph’s arboricity a. We extend our results to partial coloring and list coloring.