Distributed (Delta + 1)-coloring in linear (in Delta) time

Leonid Barenboim, Michael Elkin

The distributed (Delta + 1)-coloring problem is one of most fundamental and well-studied problems of Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there…