CONCURRENCY: PRACTICE AND EXPERIENCE
Concurrency: Pract. Exper. 2000; 12:1131–1146

Scalable parallel graph coloringalgorithms
Assefaw Hadish Gebremedhin∗,† and Fredrik Manne
Department of Informatics, University of Bergen, N-5020 Bergen, Norway

SUMMARY
Finding a good graph coloring quickly is often a crucial phase in the development of efficient, parallel
algorithms for many scientific and engineering applications. In this paper we consider the problem ofsolving the graph coloring problem itself in parallel. We present a simple and fast parallel graph coloringheuristic that is well suited for shared memory programming and yields an almost linear speedup on
the PRAM model. We also present a second heuristic that improves on the number of colors used. The
heuristics have been implemented using OpenMP. Experiments conducted on an SGI Cray Origin 2000
supercomputer using very large graphs from finite element methods and eigenvalue computations validate
the theoretical run-time analysis. Copyright  2000 John Wiley & Sons, Ltd.
KEY WORDS :graph coloring; parallel algorithms; shared memory programming; OpenMP

1. INTRODUCTION
The graph coloring problem (GCP) deals with assigning labels (called colors) to the vertices of a graphsuch that adjacent vertices do not get the same color. The primary objective is to minimize the numberof colors used. The GCP arises in a number of scientific computing and engineering applications.
Examples include, among others, timetabling and scheduling [1], frequency assignment [2], register
allocation [3], printed circuit testing [4], parallel numerical computation [5], and optimization [6].
Coloring a general graph with the minimum number of colors is known to be an NP-hard problem [7],and thus one often relies on heuristics to obtain a usable solution.
In a parallel application, graph coloring is usually performed in order to partition the work associatedwith the vertices into independent subtasks such that the subtasks can be performed concurrently.
Depending on the amount of work associated with each vertex, there are basically two coloring
strategies one can pursue. In the first strategy the emphasis is on minimizing the number of colors,∗ Correspondence to: A. H. Gebremedhin, Department of Informatics, University of Bergen, N-5020 Bergen, Norway.
† E-mail: assefaw@ii.uib.no

Copyright  2000 John Wiley & Sons, Ltd.

Received November 1999
Revised May 2000

1132

A. H. GEBREMEDHIN AND F. MANNE

whereas in the second the focus is on speed. Ascertaining which is more appropriate depends on theunderlying problem one is trying to solve.
If the task associated with each vertex is computationally expensive then it is crucial to use as few
colors as possible. There exist several time-consuming (iterative) local improvement heuristics foraddressing this need. Some of these heuristics have been shown to be parallelizable [1].
If, on the other hand, the task associated with each vertex is fairly small and one repeatedly has tofind new graph colorings, then the overall time to perform the colorings might take up a significant
portion of the entire computation. See [8] for an example of this case. In such a setting it is more
important to compute a usable coloring fast than spending time on reducing the number of colors.
For this purpose there exist several linear time-, or close to linear time-, sequential greedy coloringheuristics. These heuristics have been found to be effective in coloring graphs that arise from a number
of applications [6,9]. Because of their inherent sequential nature, however, these heuristics are difficult
to parallelize.
This paper focuses mainly on the latter strategy, where the goal is to develop scalable parallel
coloring heuristics based on greedy methods. Previous work on developing such algorithms has been
performed on distributed memory computers using explicit message passing. The speedup obtained
from these efforts has been discouraging [5]. The main justification for using these algorithms has
been access to more memory and thus the ability to solve problems with very large graphs. It is tobe noted that the current availability of shared memory computers where the entire memory can beaccessed by any processor makes this argument less significant now.
The development of shared memory computers has been accompanied by the emergence of newshared memory programming paradigms of which OpenMP has become one of the most successful
and widely used [10]. OpenMP is a directive-based, fork-join model for shared memory parallelism.
In this paper we present a fast and scalable parallel graph coloring algorithm suitable for the sharedmemory programming model. In our context, scalability of a parallel algorithm is a measure of its
capacity to increase speedup as the number of processors is increased for a given problem size. Ouralgorithm is based on first performing a parallel pseudo-coloring of the graph. The prefix ‘pseudo’ isused to reflect that the coloring might contain adjacent vertices that are colored with the same color. To
remedy this we perform a second parallel step where any inconsistencies in the coloring are detected.
These are then resolved in a final sequential step. An analysis on the PRAM model using p processors
for a graph with n vertices √and m edges shows that the expected number of conflicts from the firststage is low, and for p ≤ n/ 2m the algorithm is expected to provide a nearly linear speedup. We also
extend this idea and present a second parallel algorithm that potentially uses fewer colors.
The presented algorithms have been implemented in Fortran90 using OpenMP on a Cray Origin 2000
supercomputer. Experimental results on a number of very large graphs show that the algorithms yield
good speedup and produce colorings of comparable quality to that of their sequential counterparts. The
fact that we are using OpenMP makes our implementation significantly simpler and easier to verify
than if we had used a distributed memory programming environment such as MPI.
The rest of this paper is organized as follows. In Section 2 we give some background on thegraph coloring problem and previous efforts made to solve it in parallel. In Section 3 we describe
our new parallel graph coloring algorithms and analyze their performance on the PRAM model.
Synchronization overhead and OpenMP issues related to our implementation are discussed in Section 4.
In Section 5 we present and discuss results from experiments performed on the Cray Origin 2000.
Finally, in Section 6 we give concluding remarks.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1133

2. BACKGROUND
In this section we give a brief overview of previous work done on the development of fast coloringheuristics, both sequential and parallel. We begin by introducing some graph notation used in thispaper.
For a graph G = (V , E), we denote |V | by n, |E| by m, and the degree of a vertex vi by deg(vi ).
Moreover, the maximum, minimum, and average degree in a graph are denoted by !, δ, and δ,
respectively.
As mentioned in Section 1, there exist several fast sequential coloring heuristics that are very
effective in practice. These algorithms are all based on the same general greedy framework: a vertex
is selected according to some predefined criterion and then colored with the smallest valid color. The
selection and coloring continues until all the vertices in the graph are colored.
Some of the suggested coloring heuristics under this general framework include Largest-DegreeFirst-Ordering (LFO) [11], Incidence-Degree-Ordering (IDO) [6], and Saturation-Degree-Ordering(SDO) [12]. These heuristics choose at each step a vertex v from the set of uncolored vertices withthe maximum ‘degree’. In LFO, the standard definition of degree of a vertex is used. In IDO, incidence
degree is defined as the number of already colored adjacent vertices, whereas in SDO one only
considers the number of differently colored adjacent vertices. First Fit (FF) is yet another, simple
variant of the general greedy framework. In FF, the next vertex from some arbitrary ordering is chosen
and colored. In terms of quality of coloring, these heuristics can in most cases be ranked in increasingorder as FF, LFO, IDO, and SDO. Note that for a graph G the number of colors used by any sequential
greedy algorithm is bounded from above by ! + 1. On average, however, it has been shown that for
random graphs FF is expected to use no more than 2χ(G) colors, where χ(G) is the chromatic number‡of G [13]. In terms of run time, FF is clearly O(m), LFO and IDO can be implemented to run in O(m),and SDO in O(n2 ) [9,12].
When it comes to parallel graph coloring, a number of the existing fast heuristics are based on theobservation that an independent set of vertices can be colored in parallel. A general parallel coloring
scheme based on this observation is outlined in Scheme 1 (Figure 1).
Depending on how the independent set is chosen and colored, Scheme 1 specializes into a number ofvariants. The Parallel Maximal Independent set (PMIS) coloring is one variant. This is a heuristic basedon Luby’s maximal independent set finding algorithm [14]. Other variants are the asynchronous parallel
heuristic by Jones and Plassmann (JP) [9], and the Largest-Degree-First (LDF) heuristic developed
independently by Gjertsen Jr. et al. [15] and Allwright et al. [5].
Allwright et al. made an experimental, comparative study by implementing the PMIS, JP, and LDF
coloring algorithms on both SIMD and MIMD parallel architectures [5]. They report that they did not
get speedup for any of these algorithms.
Jones and Plassmann [9] do not report on obtaining speedup for their algorithms either. They statethat ‘the running time of the heuristic is only a slowly increasing function of the number of processors
used’.

‡ The chromatic number of a graph is the optimal number of colors required to color it.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1134

A. H. GEBREMEDHIN AND F. MANNE

Scheme 1
ParallelColoring(G = (V , E))
begin
U ←V
G% ← G
while (G% is not empty) do in parallel
Find an independent set I in G%
Color the vertices in I
U ←U \IG% ← graph induced by U
end-while
end
Figure 1. A parallel coloring heuristic.

3. BLOCK PARTITION BASED COLORING HEURISTICS
In this section we present two new parallel graph coloring heuristics and give their performance
analysis on the PRAM model. Our heuristics are based on dividing the vertex set of the graph intop successive blocks of equal size. We call this a block partitioning. We assume that the vertices arelisted in a random order and thus no effort is made to minimize the number of crossing edges. A
crossing edge is an edge whose end points end up in two different blocks. Obviously, because of theexistence of crossing edges, the coloring subproblems defined by each block are not independent.
3.1. The first algorithm
The strategy we employ consists of three phases. In the first phase, the input vertex set V of the graph
G = (V , E) is partitioned into p blocks as {V1 , V2 , . . . , Vp } such that |Vi | = n/p, 1 ≤ i ≤ p. The
vertices in each block are then colored in parallel using p processors. The parallel coloring comprises
n/p parallel steps with synchronization barriers at the end of each step. When coloring a vertex, allits previously colored neighbors, both the local ones and those found on other blocks, are taken into
account. In doing so, two processors may simultaneously attempt to color vertices that are adjacent toeach other. If these vertices are given the same color, the resulting coloring becomes invalid and hence
we call the coloring obtained a pseudo coloring. In the second phase, each processor pi checks whether
vertices in Vi are assigned valid colors by comparing the color of a vertex against all its neighbors thatwere colored at the same parallel step in the first phase. This checking step is also done in parallel. If
a conflict is discovered, one of the end points of the edge in conflict is stored in a table. Finally, in thethird phase, the vertices stored in this table are colored sequentially. Algorithm 1 provides the detailsof this strategy and is given in Figure 2.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1135

Algorithm 1
BlockPartitionBasedColoring(G, p)
begin
! "
# $
1. Partition V into p equal blocks V1 . . . Vp , where pn ≤ |Vi | ≤ pn
for i = 1 to p do in parallelfor each vj ∈ Vi do
assign the smallest legal color to vertex vj
barrier synchronize
end-forend-for
2. for i = 1 to p do in parallelfor each vj ∈ Vi dofor each neighbor u of vj that is colored at the same parallel step do
if color(vj ) = color(u) thenstore min {u, vj } in table A
end-ifend-forend-forend-for3. Color the vertices in A sequentiallyend
Figure 2. Block partition based coloring.

3.1.1. Analysis
Our analysis is based on the PRAM model. Without loss of generality we assume that n/p, the numberof vertices per processor, is an integer. Let the vertices on each processor be numbered from 1 to n/p
and the parallel time used for coloring be divided into n/p time slots. The processors are synchronizedat the end of each time unit tj . This means, at each time unit tj , that processor pi colors vertex vj ∈ Vi ,1 ≤ j ≤ n/p and 1 ≤ i ≤ p.
Our first result gives an upper bound on the expected number of conflicts (denoted by K) created at
the end of Phase 1 of Algorithm 1 for a graph in which the vertices are listed in a randomly permutedorder.
Lemma 1. The expected number of conflicts created at the end of Phase 1 of Algorithm 1 is at most%&nδ(p − 1)δ(p − 1)≈2n−12

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1136

A. H. GEBREMEDHIN AND F. MANNE

Proof. Consider a vertex x ∈ V that is colored at time unit tj , 1 ≤ j ≤ n/p. Since the neighbors of x
are randomly distributed, the expected number of neighbors of x that are concurrently colored at time
unit tj is given byp−1
deg(x)
n−1(1)

If we sum (1) over all vertices in G we count each pair of adjacent vertices that are coloredsimultaneosly twice. Moreover, each term in the sum represents only a potential conflict since two
adjacent vertices could be colored simultaneously and yet be assigned different colors. The sum thus
gives an upper bound on the expected number of conflicts. Therefore, we have
' p−1
deg(x)(2)
E[K] ≤ (1/2)
n−1
x∈V

p−1
(2m)
(3)
n−1
(4)
= (1/2)δ(p − 1)(n/n − 1)(
In going from (3) to (4), the identity δ = v∈V deg(v)/n = 2m/n is used. Note that for large valuesof n, (n/n − 1) ≈ 1 and the result follows.
= (1/2)

We now look at the expected run time§ of Algorithm 1. To do so, we introduce a graph attribute
called relative sparsity r, defined as r = n2 /m. Note that 1/r, the ratio of the actual number of edges
to the total possible number of edges, shows√the density of the graph. The following lemma states
that, for bounded degree graphs and for p ≤ (r/2), Algorithm 1 provides an almost linear speedup
compared to the sequential First Fit algorithm.

Lemma 2.√On a CREW PRAM, Algorithm 1 colors √the input graph consistently in EO(!n/p) time
when p ≤ (r/2) and in EO(!δp) time when p > (r/2).
Proof. Note first that since Phase 3 resolves all the conflicts that are discovered in Phase 2, the coloringat the end of Phase 3 is a valid one. Both Phase 1 and 2 require concurrent read capability and thus
the required PRAM is CREW. The overall time required by Algorithm 1 is T = T1 + T2 + T3 , where
Ti is the time required by Phase i. Both Phase 1 and 2 consist of n/p parallel steps. The number ofoperations in each parallel step is proportional to the degree of the vertex under investigation, which
is bounded from above by !. Thus, T1 = T2 = O(!n/p). The time required by the sequential step
(Phase 3) is T3 = O(!K), where K is the number of conflicts discovered in Phase 2. From Lemma 1,
E[K] = O(δp). Substituting yields
T = T1 + T2 + T3 = EO(!(n/p + δp))(5)

The overall time T)is thus determined by how n/p compares with δp. Using the identity δ = 2m/n,√(n2 /2m) = (r/2), the term n/p dominates, giving an overall running time of
we see that for p ≤ √EO(!n/p). For p > (r/2), the term δp dominates and the overall time becomes EO(!δp).

§ We use the prefix E to identify expected time complexity expressions.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1137

For most practical applications and currently available parallel computers we expect that both δ ) n
and p ) n, implying that n > p2 δ and thus giving an overall time complexity of O(!n/p) for
Algorithm 1.
The number of colors used by Algorithm 1 is bounded from above by ! + 1. This follows since
the conflicts that arise in Phase 1 are resolved sequentially. However, we note that there exist instanceswhere the coloring produced by Algorithm 1 can be arbitrarily worse than that of the sequential FF
algorithm. To see this, consider a complete bipartite graph G = (V1 , V2 , E) with |V1 | = |V2 | = n/2,
where the vertices in V1 are ordered before the vertices in V2 and with p = 2. For this setting Algorithm
1 will use (n/2) + 1 colors, while sequential FF will color the graph optimally using two colors.
3.2. The second algorithm
In this section we show how Algorithm 1 can be modified to use fewer colors. Our method is motivatedby the idea behind Culberson’s Iterated Greedy coloring heuristic (IG) [16]. IG is based on thefollowing result, stated here without proof.
Lemma 3. (Culberson) Let C be a k-coloring of a graph G, and π a permutation of the vertices suchthat if C(vπ(i) ) = C(vπ(l) ) = c, then C(vπ(j ) ) = c for i < j < l. Then, applying the First Fit
algorithm to G where the vertices have been ordered by π will produce a coloring using k or fewer
colors.
From Lemma 3, we see that if FF is reapplied on a graph where the vertex set is ordered such thatvertices belonging to the same color class¶ in the previous coloring are listed consecutively, the newcoloring is better or at least as good as the previous coloring. There are many ways in which the verticesof a graph can be arranged satisfying the condition of Lemma 3. One such ordering is the reverse color
class ordering [16]. In this ordering, the color classes are listed in reverse order of their introduction.
This has the potential to reduce the number of colors used since one now proceeds by first coloring
vertices that could not be colored with low values in the previous coloring.
Our improved coloring heuristic uses Lemma 3 and consists of four phases, one more phase than
Algorithm 1. The first phase is the same as Phase 1 of Algorithm 1. Let the coloring number used bythis phase be ColNum. During the second phase, the pseudo coloring of the first phase is used to get areverse color class ordering of the vertices. The second phase consists of ColNum steps. In each stepi, the vertices of color class ColNum − i − 1 are colored afresh in parallel in a similar manner as inPhase 1. The remaining two phases are the same as Phases 2 and 3 of Algorithm 1. The method justdescribed (Algorithm 2) is outlined in Figure 3.
Each color class at the end of Phase 1 is a pseudo independent set. In particular, any edge within acolor class results from a ‘conflict’ edge from Phase 1. Hence a new block partitioning of the vertices ofeach color class results in only a few crossing edges. In other words, the number of conflicts expected at
the end of Phase 2 (K2 ) should be much smaller than the number of conflicts at the end of Phase 1 (K1 ).
Thus, in addition to improving the quality of the coloring, Phase 2 should also provide a significant¶ Vertices of the same color constitute a color class.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1138

A. H. GEBREMEDHIN AND F. MANNE

Algorithm 2
ImprovedBlockPartitionBasedColoring(G, p)
begin
1. As Phase 1 of Algorithm 1{At this point we have the pseudo independent
sets ColorClass(1) . . . ColorClass(ColNum) }2. for k = ColNum down to 1 do
Partition ColorClass(k) into p equal blocks V1% . . . Vp%
for i = 1 to p do in parallelfor each vj ∈ Vi% doassign the smallest legal color to vertex vj
end-forend-forend-for
3. As Phase 2 of Algorithm 1
4. As Phase 3 of Algorithm 1
end
Figure 3. Modified block partition based coloring.

reduction in the number of conflicts. Note that conflict checking and removal steps are included inPhases 3 and 4 to ensure that any remaining conflicts are resolved.
The following result gives an upper bound on the expected number of conflicts at the end of Phase 2of Algorithm 2.
Lemma 4. The expected number of conflicts created at the end of Phase 2 of Algorithm 2 is at most
2p2 !(! + 1)/n ≈ 2p2 !2 /n.
Proof. From Lemma 1, the expected number of conflicts at the end of Phase 1 is approximately
bounded by δp/2. Noting that there are m edges in the input graph G to Algorithm 2, at the endof Phase 1, the probability that an arbitrary edge in G is in ‘conflict’ is expected to be no morethan δp/2m = p/n. Now consider a color class w from the coloring obtained at the end of Phase
1 of Algorithm 2. Let G% = (V % , E % ) be the graph induced by the vertices of this color class andlet n% = |V % |, m% = |E % |. Further, let x be a vertex in G% and deg% (x) its degree. From the above
discussion, we expect that deg% (x) ≤ (p/n)deg(x). Using the same argument as in Lemma 1, theexpected number of neighbors of x that are concurrently colored at time unit tj , for 1 ≤ j ≤ n% /p,
is p − 1/(n% − 1)deg% (x). Thus the number of conflicts created due to the vertices of color class w
Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1139(denoted by K % ) is bounded as follows:
E[K % ] ≤' p(p − 1)deg(x)(6)n(n% − 1)(p% deg(x)(7)= (p − 1) x∈V%
n
n −1
2p2 !
(8)
≤
n
Recall that there are at most ! + 1 colors at the end of Phase 1. Therefore, K2 , the total number of
expected conflicts at the end of Phase 2, isx∈V %E[K2 ] ≤2p2 !(! + 1)n(9)Noting that !(! + 1) ≈ !2 , (9) can be rewritten as
+2
* √
2p
E[K2 ] ≤ √n/!
√√This indicates that if 2p < n/!, the expected number of conflicts at the end of Phase 2 is lessthan 1.

4. IMPLEMENTATION ISSUESIn this section we address the problem of synchronization overhead and illustrate how OpenMP is usedin our Fortran90 implementations.
4.1. Synchronization overhead
The barrier synchronization in Phase 1 of Algorithm 1 is introduced to identify the parallel step tj(1 ≤ j ≤ n/p) during which a vertex is colored. This information is used for two purposes: (i) in
Phase 1 to identify already colored neighbors of a vertex, and (ii) in Phase 2 to identify the neighborsof a vertex that are colored at the same parallel step as itself. Although the barrier enables us to realize
these purposes, its implementation typically incurs an undesirable large overhead. To overcome thiswe have developed an asynchronous version of Algorithm 1 (and consequently of Algorithm 2). In
the asynchronous version we consider all the neighbors of a vertex under investigation, irrespectiveof the parallel step during which they are colored. This is done first when determining the color ofa vertex and then when checking for consistency of coloring. We have implemented and tested boththe asynchronous and synchronous versions of Algorithm 1. In the synchronous version, an OpenMP
library routine was utilized to realize barrier synchronization. The obtained results show that theasynchronous version runs faster by a factor of 3 to 5. The relative slow-down factor of the synchronous
version depends on how often the OpenMP barrier routine is called. Particularly for a given graph, therelative time spent on synchronization increases with the number of processors.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1140

A. H. GEBREMEDHIN AND F. MANNE!$omp parallel do schedule(static, Bsize)
private(i) shared(vertex)
do i = 1, number of vertices
call assign color synch(vertex(i))
call mp barrier
enddo!$omp parallel do schedule(static, Bsize)
private(i) shared(vertex)
do i = 1, number of vertices
call assign color asynch(vertex(i))
enddo

Figure 4. OpenMP-sketch of Phase 1 of Algorithm 1, synchronous (left) and asynchronous (right).

4.2. OpenMP
Figure 4 provides a sketch of Phase 1 of both the synchronous and asynchronous versions of
Algorithm 1. Here the vertices are stored in the integer array vertex and the number of vertices perprocessor is stored in the variable Bsize. The routines assign color synch(i) and assign color asynch(i),synchronous and asynchronous versions, respectively, assign the smallest valid color to vertex i.
It should be noted that, even though the synchronous algorithm visits fewer vertices both when
determining the color of a vertex and when checking for consistency, it incurs an extra initial overhead
since one must determine for each of value of p which vertices to check. The routine mp barrier is an
OpenMP library routine that enables barrier synchronization.
In addition to the standard OpenMP directives we have used data distribution directives provided by
SGI to ensure that most cache misses are satisfied from local memory.
We disallow access to a memory location while it is being written by using the ATOMIC directive
in OpenMP. This makes accessing the color of any vertex without reading garbage values possible inPhase 1.
5. EXPERIMENTAL RESULTS
In this section, we demonstrate experimentally the performance of the asynchronous versions of
Algorithms 1 and 2. In Section 5.1 we introduce the test graphs used in the experiments and in
Section 5.2 we present and discuss the experimental results. The experiments have been performed on a
Cray Origin 2000, a CC-NUMA machine consisting of 128 MIPS R10000 processors. The algorithms
have been implemented in Fortran90 and parallelized using OpenMP[10]. We have also implemented
the sequential versions of FF and IDO to use as benchmarks.
In these experiments, the block partitioning is based on the ordering of the vertices as provided in
the input graph. In other words, no random permutation is done on the ordering of the vertices prior topartitioning.
5.1. Test graphs
The test graphs used in our experiments are divided into three categories as Problem Set I, II, and III(see Table I). Problem Sets I and II consist of graphs (matrices) that arise from finite element methods.** G. Karypis. Private communication.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1141

Table I. Test graphs.
Set

Problem

n

m

!

δ

δ

√
r/2

χFF

χIDO

Set I
Set I
Set II
Set II
Set III
Set III

mrng2
mrng3
598a
m14b
dense1dense2

1 017 253
4 039 160
110 971
214 765
19 703218 849

2 015 714
8 016 848
741 934
1 679 018
3 048 477
121 118 458

4
4
26
40
504
1640

2
2
5
4
116
332

3
3
13
15
309
1106

506
1008
91
117
8
14

5
5
11
13
122
377

5
5
9
10
122
376

Problem Set III consists of matrices that arise in eigenvalue computations [8]. In addition to providing
some statistics about the structure of the test graphs, Table I also lists the number of colors required
when coloring the graphs using our sequential FF and IDO implementations (shown under columns
χFF and χIDO , respectively).
5.2. Discussion
Algorithm 1. Table II lists results obtained using the asynchronous version of Algorithm 1. The
number of blocks (processors) is given in column p. Columns χ1 and χ3 give the number of colors
used at the end of Phases 1 and 3, respectively. The number of conflicts that arise in Phase 1 arelisted in the column labeled K. The column labeled δ(p − 1)/2 gives the theoretically expected upperbound on the number of conflicts as predicted by Lemma 1. The times in milliseconds required by thedifferent phases are listed in columns T1 , T2 , T3 , and the last column Ttot gives the total time used.
The column labeled Spar lists the speedup obtained compared to the time used by running Algorithm 1
on one processor (Spar (p) = Ttot (1)/Ttot (p)). The last column, SseqFF , gives the speedup obtained bycomparing against a straightforward sequential FF algorithm (SseqFF (p) = T1 (1)/Ttot(p)).
The results in column K of Table II show that, in general, the number of conflicts that arise in Phase
1 is small and grows as a function of the number of blocks (or processors) p. This agrees well withthe result from Lemma 1. We see that for the relatively dense graphs the actual number of conflicts ismuch less than the bound given by Lemma 1.
The run times obtained show that Algorithm 1 performs as predicted by Lemma 2. Particularly, thetime required for recoloring incorrectly colored vertices is observed to be practically zero (in the orderof a few microseconds) for all our test graphs. This is not surprising as the obtained value of K is
negligibly small compared to the number of vertices in a given graph.
As results in columns T1 and T2 indicate, the time used to detect conflicts is approximately the sameas the time used to do the initial coloring. This makes the running time of the algorithm using one
processor approximately double that of the sequential FF. This in turn reduces the speedup obtained
compared to the sequential FF by a factor of 2. The speedup obtained compared to running the parallel
algorithm on one processor gets its best values for the two largest graphs mrng3 and dense2.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1142

A. H. GEBREMEDHIN AND F. MANNE

Table II. Experimental results for Algorithm 1.
Problem

p

χ1

χ3

K

mrng2
mrng2
mrng2
mrng2
mrng2
mrng3
mrng3
mrng3
mrng3
mrng3
598a
598a
598a
598a
598a
m14b
m14b
m14b
m14b
m14b
dense1dense1dense1dense1dense1dense2dense2dense2dense2dense2

1
2
4
8
12
1
2
4
8
12
1
2
4
8
12
1
2
4
8
12
1
2
4
8
12
1
2
4
8
12

5
5
5
5
5
5
5
5
5
5
11
12
12
12
12
13
13
14
13
13
122
142
137
129
121
377
382
400
407
399

5
5
5
5
5
5
5
5
5
5
11
12
12
12
12
13
13
14
13
13
122
142
137
129
124
377
382
400
407
399

0
0
0
8
18
0
2
4
0
12
0
4
12
36
42
0
2
14
16
36
0
30
94
94
78
0
68
98
254
210

#

δ(p−1)
2

0
2
5
11
17
0
2
5
11
17
0
7
20
46
72
0
8
23
53
83
0
155
464
1082
1700
0
553
1659
3871
6083

$

T1

T2

T3

Ttot

Spar

SseqFF

1190
1130
430
260
200
4400
2250
1300
630
430
100
55
40
28
20
200
130
80
48
40
200
110
69
53
55
9200
5160
2600
1590
1090

1010
970
280
200
130
3400
1600
1000
800
480
80
40
20
15
15
180
120
50
26
20
290
140
72
44
90
13 200
8040
4080
2280
1420

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
3
4
11
8

2200
2100
710
460
330
7800
3850
2300
1430
910
180
95
60
43
35
380
250
130
74
60
490
250
141
97
145
22 40013 203
6684
3881
2518

1
1.1
3.1
4.8
6.7
1
2
3.4
5.5
8.6
1
2
3
4.2
5.2
1
1.5
3
5
6.4
1
2
3.5
5.6
3.4
1
1.7
3.4
5.8
9

0.6
0.6
1.7
2.6
3.6
0.6
1.1
1.9
3.1
4.8
0.6
1.1
1.7
2.3
2.9
0.5
0.8
1.5
2.7
3.3
0.4
0.8
1.4
2.1
1.4
0.4
0.7
1.4
2.4
3.7

We see that the number of colors used by Algorithm 1 varies with the number of processors used.
Comparing column χ3 of Table II and column χFF of Table I, we see that the deviation of χ3 from χFF
is at most 1 for graphs from Problem Sets I and II and at most 16% for the two graphs from Problem
Set III.
Algorithm 2. Table III lists results of the asynchronous version of Algorithm 2. The number of colors
used at the end of Phases 1 and 2 are listed in columns χ1 and χ2 , respectively. The coloring at theend of Phase 2 is not guaranteed to be conflict-free. Phases 3 and 4 detect and resolve any remaining
conflicts. Column χ4 lists the number of colors used at the end of Phase 4. The number of conflicts
Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1143

Table III. Experimental results for Algorithm 2.
Problem

p

χ1

χ2

χ4

K1

K2

T1

T2

T3

T4

Ttot

Spar

S2seqFF

mrng2
mrng2
mrng2
mrng2
mrng2
mrng3
mrng3
mrng3
mrng3
mrng3
598a
598a
598a
598a
598a
m14b
m14b
m14b
m14b
m14b
dense1dense1dense1dense1dense1dense2dense2dense2dense2dense2

1
2
4
8
12
1
2
4
8
12
1
2
4
8
12
1
2
4
8
12
1
2
4
8
12
1
2
4
8
12

5
5
5
5
5
5
5
5
5
5
11
12
11
12
12
13
13
14
13
13
122
135
132
126
123
377
376
394
398
399

5
5
5
5
5
5
5
5
5
5
10
10
10
11
11
11
12
12
12
11
122
122
122
122
121
376
376
376
376
376

5
5
5
5
5
5
5
5
5
5
10
10
10
11
11
11
12
12
12
11
122
122
122
122
122
376
376
376
376
376

0
0
2
16
12
0
0
0
4
24
0
14
22
40
50
0
2
6
12
22
0
26
40
104
150
0
66
112
164
232

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
2

1050
950
470
300
250
3700
1890
1100
540
450
100
65
35
30
30
200
105
70
45
53
180
100
80
70
40
9920
5200
2700
2000
1100

1700
1350
840
500
400
9500
4100
2700
1800
1900
200
105
90
99
110
520
240
160
120
150
250
180
100
80
760
13 700
6220
3600
2000
1700

820
650
310
200
170
2600
1200
750
450
300
75
37
20
25
15
190
80
40
25
20
180
140
70
30
30
7500
4200
2100
1800
900

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

3570
2650
1620
1000
820
15800
7190
4550
2790
2650
375
207
145
154
155
910
425
270
190
223
610
420
250
180
830
31120
15620
8400
5800
3700

1
1.4
2.2
3.6
4.4
1
2.2
3.5
5.6
6
1
1.8
2.6
2.4
2.4
1
2.1
3.4
4.8
4
1
1.5
2.5
3.4
0.7
1
2
3.7
5.4
8.4

0.8
1.0
1.7
2.8
3.4
0.8
1.8
2.9
4.7
5.0
0.8
1.5
2.1
2.0
2.0
0.8
1.7
2.7
3.8
3.2
0.7
1.0
1.7
2.4
0.5
0.8
1.5
2.8
4.0
6.4

at the end of Phases 1 and 2 are listed in columns K1 and K2 , respectively. The time elapsed (inmilliseconds) in the various stages is given in columns T1 , T2 , T3 , T4 , and Ttot . In order not to obscurespeedup results, the time required to build the color classes prior to Phase 2 is not included in T2 . In
general the time used for this purpose is in the order of 20% of T1 . Speedup values in column Spar are
calculated as in the corresponding column of Table II. The column S2seqFF gives speedups as comparedto Culberson’s IG restricted only to two iterations (S2seqFF = T1 (1) + T2 (1)/Ttot (p)).
Results in column χ2 confirm that Phase 2 of Algorithm 2 reduces the number of colors used by
Phase 1. This is especially true for test graphs from Problem Sets II and III, which contain denser
graphs than Problem Set I. Comparing the results in column χ2 with the results in columns χFF and
Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1144

A. H. GEBREMEDHIN AND F. MANNE

12
s=p
s=p/2
s=2p/3s (Alg1)
pars(Alg1)seqFFs (Alg2)
pars(Alg2)
2seqFF

10

speedup (s)

8

6

4

2

0

0

2

4
6
8
number of processors (p)1012Figure 5. Comparison of speedup curves for dense2.

χIDO of Table I, we see that in general the quality of the coloring obtained using Algorithm 2 is neverworse than that of sequential FF and in most cases is comparable with that of the IDO algorithm. IDO
is known to be one of the most effective coloring heuristics [6]. We also observe that, unlike Algorithm
1, the number of colors used by Algorithm 2 remains reasonably stable as the number of processors isincreased.
From column K2 we see that the number of conflicts that remains after Phase 2 of Algorithm 2 iszero for almost all test graphs and values of p. The only occasion where we obtained a value otherthan zero for K2 was using p = 12 for the graphs dense1 and dense2. These results agree well withthe claim in Lemma 4.
Figure 5 shows the speedup obtained for the problem dense2 using Algorithm 1 and 2 and how theobtained results compare with the ideal speedups.

6. CONCLUSION
We have presented two new parallel graph coloring heuristics suitable for shared memory programming
and analyzed their performance using the PRAM model.
The heuristics have been implemented using OpenMP, and experiments conducted on an SGI Cray
Origin 2000 supercomputer using very large graphs validate the theoretical analysis.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

SCALABLE PARALLEL GRAPH COLORING ALGORITHMS

1145

The first heuristic is fast, simple and yields reasonably good speedup for graphs of practical interest
run on a realistic number of processors. Generally, the number of colors used by this heuristic neverexceeds !+1. For relatively dense graphs, the number of colors used by the heuristic increases slightly
as more processors are applied.
The second heuristic is relatively slow, yields reasonable speedup and improves on the quality ofcoloring obtained from the first one in that it uses fewer colors. The number of colors used is also morestable as the number of processors is increased. For the test graphs used in this experiment, the numberof colors used by this heuristic is in most cases comparable with that of sequential IDO.
One of the main arguments against using OpenMP has been that it does not give as good speedup
as a more dedicated message passing implementation using MPI. The results in this paper show an
example where the opposite is true: the OpenMP algorithms have better speedup than existing message
passing based algorithms. Moreover, implementing the presented algorithms in a message passing
environment would have required a considerable effort and it is not clear if this would have led toefficient algorithms. Implementing these algorithms using OpenMP is a relatively straightforward task
as all the communication is hidden from the programmer.
We point out that in a recent development the algorithms presented in this paper have been adapted
to the CGM model [17].
We believe that the general idea in these coloring heuristics of allowing inconsistency for the sakeof concurrency can be applied to develop parallel algorithms for other graph problems, and we are
currently investigating this in problems related to sparse matrix computations.
ACKNOWLEDGEMENTS

We thank the referees for their helpful comments and George Karypis for making the test matrices in Problem Sets
I and II available.

REFERENCES
1. Lewandowski G. Practical implementations and applications of graph coloring. PhD Thesis, University of WisconsinMadison, August 1994.
2. Gamst A. Some lower bounds for a class of frequency assignment problems. IEEE Transactions of Vehicular Technology
1986; 35(1):8–14.
3. Chaitin GJ, Auslander M, Chandra AK, Cocke J, Hopkins ME, Markstein P. Register allocation via coloring. Computer
Languages 1981; 6:47–57.
4. Garey MR, Johnson DS, So HC. An application of graph coloring to printed circuit testing. IEEE Transactions on Circuits
and Systems 1976; 23:591–599.
5. Allwright JR, Bordawekar R, Coddington PD, Dincer K, Martin CL. A comparison of parallel graph coloring algorithms.
Technical Report SCCS-666, Northeast Parallel Architecture Center, Syracuse University, 1995.
6. Coleman TF, More JJ. Estimation of sparse jacobian matrices and graph coloring problems. SIAM Journal on Numerical
Analysis 1983; 20(1):187–209.
7. Garey MR, Johnson DS. Computers and Intractability. W. H. Freeman: New York, 1979.
8. Manne F. A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices (extended abstract).
(Lecture Notes in Computer Science, vol. 1541). Springer, 1998; 332–336.
9. Jones MT, Plassmann PE. A parallel graph coloring heuristic. SIAM Journal of Scientific Computing 1993; 14(3):654–669.
10. OpenMP. A proposed industry standard api for shared memory programming. http://www.openmp.org/.
11. Welsh DJA, Powell MB. An upper bound for the chromatic number of a graph and its application to timetabling problems.
Computer Journal 1967; 10:85–86.
12. Brelaz D. New methods to color the vertices of a graph. Communications of the ACM 1979; 22(4):251–256.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146

1146

A. H. GEBREMEDHIN AND F. MANNE

13. Grimmet GR, McDiarmid CJH. On coloring random graphs. Mathematical Proceedings of the Cambridge PhilosophicalSociety 1975; 77:313–324.
14. Luby M. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing 1986;
15(4):1036–1053.
15. Gjertsen Jr. RK, Jones MT, Plassman P. Parallel heuristics for improved, balanced graph colorings. Journal of Parallel andDistributed Computing 1996; 37:171–186.
16. Culberson JC. Iterated greedy graph coloring and the difficulty landscape. Technical Report TR 92-07, Department ofComputing Science, The University of Alberta, Edmonton, Alberta, Canada, June 1992.
17. Gebremedhin AH, Lassous IG, Gustedt J, Telle JA. Graph coloring on a coarse grained multiprocessor. Presented at WG
2000, 26th International Workshop on Graph-Theoretic Concepts in Computer Science, 15–17 June 2000, Konstantz,
Germany.

Copyright  2000 John Wiley & Sons, Ltd.

Concurrency: Pract. Exper. 2000; 12:1131–1146