Simple and Near-Optimal Distributed Coloring for Sparse Graphs

Mohsen Ghaffari, Christiana Lymouri

Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with $\Delta +1$ colors, where $\Delta$ denotes the m…