High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality

Maciej Besta, Armon Carigiet, Zur Vonarburg-Shmaria +3

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 ver…