Brooks Coloring in Parallel
Peter I. Hajnal, Endre Szemerédi · SIAM Journal on Discrete Mathematics · 1990
A theorem of Brooks guarantees that a maximum-degree-D graph can be properly colored with D colors if the graph does not contain a large complete subgraph. It is proved that finding such a coloring is in NC.