An Optimal Decentralized $(\Delta +1)$-Coloring Algorithm

Daniel Bertschinger, Johannes Lengler, Anders Martinsson +4

Consider the following simple coloring algorithm for a graph on $n$ vertices. Each vertex chooses a color from $\{1,\dots ,\Delta (G)+1\}$ uniformly at random. While there exists a c…