Faster Distributed $\Delta$-Coloring via Ruling Subgraphs

Yann Bourreau, Sebastian Brandt, Alexandre Nolin

Brooks' theorem states that all connected graphs but odd cycles and cliques can be colored with $\Delta$ colors, where $\Delta$ is the maximum degree of the graph. Such colorings have been s…