  We develop the first parallel graph coloring heuristics with strong
theoretical guarantees on work and depth and coloring quality. The key idea is
to design a relaxation of the vertex degeneracy order, a well-known graph
theory concept, and to color vertices in the order dictated by this relaxation.
This introduces a tunable amount of parallelism into the degeneracy ordering
that is otherwise hard to parallelize. This simple idea enables significant
benefits in several key aspects of graph coloring. For example, one of our
algorithms ensures polylogarithmic depth and a bound on the number of used
colors that is superior to all other parallelizable schemes, while maintaining
work-efficiency. In addition to provable guarantees, the developed algorithms
have competitive run-times for several real-world graphs, while almost always
providing superior coloring quality. Our degeneracy ordering relaxation is of
separate interest for algorithms outside the context of coloring.
