\begin{abstract} 
We present a scalable framework for parallelizing greedy graph
coloring algorithms on distributed-memory computers.  The framework
unifies several existing algorithms and blends a variety of techniques
for creating or facilitating concurrency.  The latter techniques
include exploiting features of the initial data distribution,
the use of speculative coloring and randomization, and a BSP-style
organization of computation and communication.  We experimentally
study the performance of several specialized algorithms designed using
the framework and implemented using MPI.  The experiments are
conducted on two different platforms and the test cases include
large-size synthetic graphs as well as real graphs drawn from various
application areas.  Computational results show that implementations
that yield good speedup while at the same time using about the same
number of colors as a sequential greedy algorithm can be achieved by
setting parameters of the framework in accordance with the size and
structure of the graph being colored.  Our implementation is freely
available as part of the Zoltan parallel data management and
load-balancing library.
\end{abstract}