Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM

AbstractGiven a graph, in which degree of every node is at most Δ > 2, we give an algorithm for vertex colouring it with Δ colours on the Exclusive Read Exclusive Write PRAM model (assuming, of course, that the graph does not contain a (Δ + 1)-clique), that for bounded values of Δ, takes O(log|V|) time with |V|/log|V| processors. For general values of Δ, the algorithm takes O(Δ2logΔlog |V|) time with |V|/log|V processors