  Graph coloring has been broadly used to discover concurrency in parallel
computing. To speedup graph coloring for large-scale datasets, parallel
algorithms have been proposed to leverage modern GPUs. Existing GPU
implementations either have limited performance or yield unsatisfactory
coloring quality (too many colors assigned). We present a work-efficient
parallel graph coloring implementation on GPUs with good coloring quality. Our
approach employs the speculative greedy scheme which inherently yields better
quality than the method of finding maximal independent set. In order to achieve
high performance on GPUs, we refine the algorithm to leverage efficient
operators and alleviate conflicts. We also incorporate common optimization
techniques to further improve performance. Our method is evaluated with both
synthetic and real-world sparse graphs on the NVIDIA GPU. Experimental results
show that our proposed implementation achieves averaged 4.1x (up to 8.9x)
speedup over the serial implementation. It also outperforms the existing GPU
implementation from the NVIDIA CUSPARSE library (2.2x average speedup), while
yielding much better coloring quality than CUSPARSE.
