DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1
DAVID G. HARRIS2 , JOHANNES SCHNEIDER3 , AND HSIN-HAO SU4

arXiv:1603.01486v4 [cs.DS] 17 Jan 2018

Abstract
We give a new randomized
distributed algorithm for (∆+1)-coloring in the LOCAL model, running
√
√
O(
log
log
n)
rounds in a graph of maximum degree ∆. This implies that the (∆+1)in O( log ∆)+2
coloring problem is easier than the maximal
set problem
 and the maximal matching
 independent
q

log n
log ∆
by Kuhn, Moscibroda, and
problem, due to their lower bounds of Ω min
log log n , log log ∆
Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each
node contains ∆ + 1 colors. We extend the set of distributed symmetry-breaking techniques by
performing a decomposition of graphs into dense and sparse parts.

Categories and Subject Descriptors: G.2.2 [Graph Theory]: Graph Algorithms; F.2.2 [Nonnumerical Al- gorithms and Problems]: Computations on Discrete Structures
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Distributed Networks, Vertex Coloring
1. Introduction
Given a graph G = (V, E), let n = |V | denote the number of vertices and let ∆ denote the
maximum degree. The k-coloring problem is to assign each vertex v a color χ(v) ∈ {1, 2, . . . , k}
such that no two neighbors are assigned the same color.
In this paper, we study the (∆ + 1)-coloring problem in the distributed LOCAL model. In this
model, vertices host processors and operate in synchronized rounds. In each round, each vertex
sends a message of arbitrary size to each of its neighbors, receives messages from its neighbors, and
performs (unbounded) local computations. The time complexity of an algorithm is measured by the
number of rounds until every vertex commits its output – in our case, its color. The LOCAL model
is a model for investigating what local information is needed for each vertex to compute its own
output. An r-round algorithm in the LOCAL model implies that each vertex only uses information
in its r-neighborhood to compute the output, and vice versa.
Graph coloring is one of the central problems of graph theory, with numerous applications to
algorithms and combinatorics. The (∆ + 1)-coloring problem is the most celebrated case, because
for every graph there exists a (∆ + 1) coloring, which can be found via a simple (sequential) greedy
algorithm. Furthermore, even if ∆-colorings exist for some graphs, there are examples where it
cannot be solved locally; for example, 2-coloring a ring requires Ω(n) rounds.
Vertex-coloring in the distributed model, in particular, has applications as a subroutine in other
distributed algorithms (for example, the Lovász Local Lemma [19]) and scheduling problems (for
1

This is an extended version of a paper which appeared in the 2016 Symposium on Theory of Computing (STOC)
Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported in part
by NSF Awards CNS-1010789 and CCF-1422569. Email: davidgharris29@gmail.com.
3
University of Liechtenstein, Vaduz, Liechtenstein. Email: johannes.schneider@uni.li.
4
University of North Carolina at Charlotte. Part of the work was done while at MIT and University of Michigan, supported by NSF Awards CCF-0939370, CCF-1217338, BIO-1455983, and AFOSR FA9550-13-1-0042. Email:
hsinhaosu@uncc.edu.
2

1

2

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

Bounds Randomized
√
√
log log n) [This paper]
O( log ∆) + 2O(
√
log
log n)
O(
[8]
O(log ∆) +√2
O(log ∆ + log n)
[50]
O(log
n)
[37,
1,
30]
Upper

Deterministic
√
O( ∆ log2.5 ∆ + log∗ n)
[20]
O(∆3/4 log ∆ + log∗ n)
[3]
∗
O(∆ + log n)
[7]
O(∆ log ∆ + log∗ n)
[33]
O(∆2 + log∗ n)
[34, 24]
O(∆ log n)
[24]
∗
O(∆)
∆ √ + O(log n)
[23]
2O( log n)
[43]
Lower
Ω(log∗ n)
[42] Ω(log∗ n)
[34]
Table 1. Comparison of (∆ + 1)-coloring algorithms and lower bounds
example, radio network broadcasts [13, 15, 46, 18]). It is typical in such applications that solution
quality depends on the number of colors used. Thus (∆ + 1)-coloring is a natural problem, as it
leads to the optimal schedules that one can hope to guarantee as a function of ∆.
1.1. Previous results on distributed graph coloring. The distributed coloring problem, and
variants, have a long history dating back to the 1980’s. Table 1 summarizes the results for the
most prominent coloring problem, i.e. (∆ + 1)-coloring. Several deterministic algorithms have been
developed with a run-time of O(f (∆) + log∗ n) [3, 7, 33, 34, 24, 23]. The latter term is necessary
as 3-coloring a ring require Ω(log∗ n) rounds for both deterministic and randomized algorithms
[34, 42]. A breakthrough by Barenboim
gave an algorithm running in O(∆3/4 log ∆ + log∗ n)
√ [3] 2.5
rounds, subsequently improved to O( ∆ log ∆ + log∗ n) by Fraigniaud et al. [20]. These bounds
have a sublinear dependence on ∆, which is notable since Ω(∆) lower bounds hold for related
problems in more restrictive settings [25, 28, 29, 33, 52].
The randomized algorithms considered in this paper are those which return a correct answer
0
w.h.p. (with high probability, which is with probability at least 1 − n−K , where K 0 is an arbitrary
constant K 0 > 0.) Randomized approaches can be traced back to the O(log n) rounds maximal
independent set (MIS) algorithm of Alon, Babai, and Itai [1] and Luby [37]. The O(log n)√upper
bound lasted until Schneider and Wattenhofer gave an algorithm of running
time O(log ∆+ log n)
√
log
log
n)
O(
. All these algorithms
[50]. Then, Barenboim et al. [8] improved the dependence on n to 2
require Ω(log n) rounds when ∆ = nc for some constant 0 < c ≤ 1.
√
√
1.2. Our contributions. We give a randomized algorithm running in time O( log ∆)+2O( log log n)
rounds w.h.p., which is the first algorithm that runs in o(log n) rounds for every graph. Moreover,
this implies a separation between the (∆ + 1)-coloring and the MIS problem. We elaborate our
contributions in the following:

(1) Separation between the coloring problem and the MIS problem. The coloring
problem and the MIS problem are closely related; for example, given a (∆ + 1)-coloring one
can compute a MIS in ∆ + 1 rounds by letting a node with color i join the MIS in round i (if
no neighbor joined previously). Conversely, Lovász describes how any MIS algorithm can be
used for (∆ + 1)-coloring in the same running time by simulating it on a blow-up graph [36]
(this result has also been mentioned in [37] and [1]).
Kuhn, Moscibroda, and Wattenhofer
√
O(
log
n
log log n) for which computing an MIS
[32] constructed a family of graphs with ∆ =q
2
or a maximal matching requires at least Ω( logloglogn n ) rounds. To this date, it has been
unclear whether (∆ + 1)-coloring, MIS and maximal matching are equally hard problems.
As our algorithm computes (∆+1)-colorings in the above graphs in O((log n log log n)1/4 )
rounds, we show that (∆ + 1)-coloring is an easier problem.

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

3

(2) Breaking the O(log n) barrier. From a technical perspective, the union bound barrier
for randomized distributed algorithms was observed in [6]. Roughly speaking, randomized
algorithms generally conduct a series of trials at each vertex. When the trial at a vertex
succeeds for the first time, then it commits its output. If the failure probability of each trial
is at least p, then it takes Ω(log1/p (1/δ)) trials to ensure a vertex succeed with probability
at least 1 − δ for 0 < δ < 1. However, since we require all the nodes to correctly output
their answers at the end of the algorithm, δ has to be bounded by 1/ poly(n) in order to
take the union bound over every vertex. Therefore, many randomized algorithms require
at least Ω(log1/p n) rounds.
Barenboim et al. [3] used the graph shattering technique to circumvent the union bound
barrier. The basic idea is to run the experiments for Ω(log1/p ∆) rounds so that the probability each vertex failed is at most 1/ poly(∆) after this first phase. The size of each connected
component in the graph induced by unsuccessful vertices then becomes polylog(n). Then,
one may run a deterministic algorithm on each component in parallel in the second
√ phase.
The running time of Panconesi and Srinivasan’s deterministic algorithm is 2O( log N ) on
graphs of size N [43]. Since the size of the component is exponentially
smaller than the
√
log
log n) .
O(
original graph, the running time scales down correspondingly to be 2
The graph shattering technique does not directly apply to (∆ + 1)-coloring, since every
algorithm up to this date has had a failure probability per round (and node) lower-bounded
by constants. To appreciate the difficulty of achieving sub-constant failure probability,
consider the following natural approach to the (∆ + 1)-coloring problem: each vertex selects
a color randomly and commits to the color if no neighbors has selected the same color. If
the graph contains a clique of size ∆, then the probability that a vertex in the clique
1
)∆ = Θ(1). (The MIS problem is even harder, and it
successfully colors itself is (1 − ∆+1
was only recently shown by [21] how to achieve amortized constant failure probability in
O(1) rounds.)
To break the O(log n) barrier, we introduce novel ideas to address symmetry-breaking
problems. We develop a network decomposition that splits a graph into sparse and dense
parts and tackles them separately. The key is that vertices boost their probability of getting
colored by using either the properties of dense parts or those of sparse parts (see Section
1.3). Our algorithm does not directly use graph shattering, although we use a number of
previous algorithms as subroutines which do use this technique.
Our algorithm extends to a closely related generalization of the vertex-coloring problem known as
list-coloring. Here, there is a set of colors C, and each vertex is equipped with a palette Pal(v) ⊆ C
of size | Pal(v)| ≥ ∆ + 1; each vertex selects one color from its palette, and no two neighbors can be
assigned the same color. (∆ + 1)-coloring is a special case in which C = {1, . . . , ∆ + 1} and every
vertex has the same palette of size ∆ + 1.
1.3. Technical summary. The possibility of coloring a vertex with super-constant probability
was first observed in [50, 17], in the setting where there are (1 + Ω())∆ colors for some  > 0.
The idea is that vertices try for multiple colors on each trial, if the palette size exceeds a node’s
degree. This yields a O(log(1/) + log∗ n) rounds algorithm for the first
phase. Combined with the
√
log
log
n) rounds. Elkin, Pettie,
O(
graph shattering technique, the algorithm runs in O(log(1/)) + 2
and Su [17]
in at most
 observed that if a graph is (1 − )-locally-sparse (each vertex participates
2 ))∆ colors.
(1 − ) ∆
triangles),
then
it
can
be
reduced
to
the
coloring
problem
with
(1
+
Ω(
2
It is thus the dense parts of the graph that become bottlenecks. However, if a subgraph is
dense, then it is likely to have small (weak) diameter. (The weak diameter of a subgraph H is the
maximum distance measured in G between any pair of vertices u, v ∈ H.) A single vertex in H can
read in all the information in H, make a decision, and broadcast it to H in time proportional to
its weak diameter.

4

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

We develop a network decomposition procedure based on local sparseness. Our decomposition
algorithm is targeted towards identifying dense components of constant weak diameter and sparse
components in a constant number
 of rounds. Roughly speaking, a sparse vertex is one which
∆
participates in at most (1 − ) 2 triangles in its neighborhood, where  > 0 is a parameter that
we will carefully choose. At the same time, we would also like to bound the number of neighbors of
a dense component that are not members of the dense component itself, called external neighbors.
This step is necessary to bound the influence of color choices of nodes in one component on other
components. This mechanism may help to leverage algorithms for other distributed problems that
can handle either dense or sparse graphs well.
First, we ignore the sparse vertices. Since each dense component has constant weak diameter,
it can elect a leader to assign a color to every member so that no intra-component conflicts occur,
i.e. the endpoints of the edges inside the same component are always assigned different colors.
Meanwhile, we hope that the assignments are random enough so that the chance of inter-component
conflicts will be small. Combined with the property of the decomposition that the number of
external neighbors is bounded, we show that the probability that a vertex remains uncolored is
roughly O() in each round. After O(log1/ ∆) rounds, the degree of each vertex becomes sufficiently
small so that the algorithm of Barenboim et al. [3] can handle the residual graph efficiently.
For the sparse vertices we analyze a preprocessing initial coloring step of the algorithm. In a
similar vein as [17], we show that there will be an Ω(2 ∆) gap between the palette size and the
degree due to the sparsity. The gap remains while the dense vertices are colored. So, we will
be able to color the √
sparse vertices by using the algorithm of Elkin et al. [17], which requires
In contrast to [17], our analysis generalizes to the listO(log(1/)) + exp(O( log log n)) rounds.
√
log
∆)
−Θ(
, we balance the round complexity between the dense
coloring problem. By setting  = 2
part and the sparse part, yielding the desired running time.
The main technical challenge lies in the dense components. In each component, we need to
generate a random proper coloring so that each vertex has a small probability of receiving the same
color as one of its external neighbors. We give a process for generating a proper coloring where the
probability that a vertex gets any color from its palette is close to uniform. Additionally, we need
to show that the structure of the decomposition is maintained in the next round for appropriately
scaled-down parameters.
1.4. Overview. In Section 2, we review related algorithms for network decomposition and coloring.
In Section 3, we state our network decomposition.
In Section 4, we outline the full algorithm for list-coloring. It consists of two steps: an initial
coloring step applied to all vertices, and multiple rounds of dense coloring.
In Section 5, we describe the initial coloring step for creating the gap between the palette size
and the degree for sparse vertices.
In Section 6, we describe a single round of the dense coloring procedure and analyze the behavior
of the graph structure.
In Section 7, we finish our analysis by solving recurrence relations for dense components which
yields the overall algorithm run time.
In Section 8, we apply the initial coloring step to give a full algorithm for locally-sparse graphs;
this extends the algorithm of [17] to list-coloring.
2. Related work
A variety of network decompositions have been developed to solve distributed computing problems. Awerbuch et al. [2] introduced the notion of (d, c)-decompositions where each component
has diameter √d and the contracted
graph is c-colorable. They give a deterministic procedure to
√
log
n
log
log
n)
O(
log
n
log
log n) )-decomposition, which can be used to deterministically
O(
,2
obtain a (2
√
compute a (∆ + 1)-coloring and MIS in 2O( log n log log n) rounds. Panconesi and Srinivasan [43]

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1
√

√

5

√

showed how to obtain a (2O( log n) , 2O( log n) )-decomposition, yielding 2O( log n) -time algorithms
for (∆ + 1)-coloring and MIS. Linial and Saks [35] gave a randomized algorithm for obtaining a
(O(log n), O(log n))-decomposition in O(log2 n) rounds. Barenboim et al. [6] gave a randomized
algorithm for obtaining (O(1), O(n ))-decompositions in constant rounds.
Reed [47] introduced the structural decomposition to study the chromatic number of graphs
of bounded clique size (see [39] for a detailed exposition). This was later used for applications
including total coloring, frugal coloring, and computation of the chromatic number [48, 41, 38, 40].
Our network decomposition method is inspired by theirs in the sense that they showed a graph can
be decomposed into a sparse component and a number of dense components. However, as their
main goal was to study the existential bounds, the properties of the decomposition between our
needs are different. For example, the diameter is an important constraint in our case. Also, our
decomposition must be computable in parallel, while theirs is obtained sequentially.
The (∆ + 1)-coloring algorithms are briefly summarized in Table 1. Barenboim and Elkin’s
monograph [5] contains an extensive survey of coloring algorithms. Faster algorithms are available
if we use more than (∆ + 1) colors. For deterministic algorithms, Linial [34] and Szegedy and
Vishwanathan [52] gave algorithms for obtaining a O(∆2 )-coloring in O(log∗ n) rounds. Barenboim
and Elkin [4] showed how to obtain an O(∆1+ )-coloring in O(log ∆ · log n) rounds. For randomized
algorithms, Schneider and Wattenhofer [50] showed that an O(∆ log(k) n + log1+1/k n)-coloring can
be obtained in O(k) rounds. Combining
the results in [50] with Kothapalli et al. [31], an O(∆)√
log
n)
rounds.
Barenboim et al. [8] showed it can be improved to
coloring
can
be
obtained
in
O(
√
O(
log
log
n)
2
rounds.
On the other hand, sparse-type graphs can be colored using significantly less than (∆ + 1) colors.
Panconesi and his co-authors [27, 16, 26, 44] developed a line of randomized algorithms for edgecoloring (i.e. coloring the line graph, which is sparse) and Brook-Vizing colorings in the distributed
setting. For example, [27] showed a O( log∆∆ )-coloring for girth-5 graphs in O(log n) rounds, provided
∆ = (log n)1+Ω(1) ; this was generalized to triangle-free graphs by Pettie and Su [45]. The restriction
on the size of ∆ can be removed via the distributed Lovász Local Lemma [14].
Schneider et al. [49] investigated distributed coloring where the number of colors used depends on
1
the chromatic number χ(G). Their algorithm requires (1− O(χ(G))
)·(∆+1) colors and running time
∗

∗

of O(log χ(G) + log∗ n) for graphs with ∆ = Ω(log1+1/ log n n) and χ(G) = O(∆/ log1+1/ log n n).
More efficient algorithms for (∆ + 1)-coloring exist for very dense graphs, e.g. a deterministic
O(log∗ n) algorithm for growth bounded graphs (e.g. unit disk graphs) [51], as well as for many
types of sparse graphs [8, 17, 45], e.g. for graphs of low arboricity. Elkin et al. [17] described a
(∆+1)-coloring algorithm for locally-sparse graphs. We will extend this result to cover list-colorings
as well.
As we have discussed, the MIS problem and the coloring problems
√ are related. An MIS can
∗
log n) rounds randomly [43].
O(
be computed in O(∆ + log n) rounds deterministically [7] and in 2
√
More recently, Ghaffari [21] reduced the randomized complexity of MIS to O(log ∆) + 2O( log log n) .
Whether an MIS can be obtained in polylogarithmic deterministic time or sublogarithmic randomized time remain interesting open problems.

3. Network decomposition and sparsity
In this section, we define a structural decomposition of the graph G into sparse and dense
vertices. We measure these notions with respect to a parameter  ∈ [0, 1].
Definition 3.1 (Friend edge). An edge uv is a friend edge if u and v share at least (1 − )∆
neighbors, i.e. |N (u) ∩ N (v)| ≥ (1 − )∆. We define F ⊆ E to be the set of friend edges.
For any vertex u, vertex v is a friend of u if uv ∈ F ; we denote the friends of u by F (u).

6

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU
d(v) ≤ ϵ∆

C1

C2

Ck

a(v)≤3ϵ∆

Vsparse

Figure 1. An illustration of a network decomposition.
Definition 3.2 (Dense and sparse vertices). A vertex v ∈ V is dense if it has at least (1 − )∆
friends. Otherwise, it is sparse.
We write V dense ⊆ V for the set of dense vertices in G, and V sparse for the set of sparse vertices
in G.
Next, we define the weak diameter ; this measures the diameter of a subgraph, while allowing
shortcuts using nodes from the original graph.
Definition 3.3 (Weak diameter). Let H ⊆ G be an induced subgraph of G. For vertices u, v ∈ V ,
let d(u, v) denote the distance between u and v in G. The weak diameter of H is defined to be
maxu,v∈H d(u, v).
Let C1 , . . . , Ck be the connected components of the subgraph H = (V dense , EH ) ⊆ G, where
EH = {uv | u, v ∈ V dense and uv ∈ F }. That is, they are the connected components induced by
friend edges and dense vertices. The vertices of G are partitioned disjointly as V = V sparse tV dense =
V sparse t C1 t · · · t Ck . We refer to each component Cj as an almost-clique. See Figure 1.
Lemma 3.4. Suppose  < 1/5. Then, for any vertices x, y ∈ Cj , we have |N (x)∩N (y)| ≥ (1−2)∆.
Proof. As x, y are in the same component Cj , there is a path of friend edges x = u0 , . . . , ut = y
connecting them. We claim that |N (x) ∩ N (ui )| ≥ (1 − 2)∆ for all i ≥ 1. We will show this by
induction on i. The base case i = 1 follows as xu1 is a friend edge.
Now, consider the induction step. As ui−1 ui is a friend, |N (ui ) ∩ N (ui−1 )| ≥ (1 − )∆. By the
induction hypothesis, |N (x) ∩ N (ui−1 )| ≥ (1 − 2)∆. We thus have:
|N (x) ∩ N (ui )| ≥ |N (x) ∩ N (ui−1 ) ∩ N (ui )|
= |N (ui−1 ) ∩ N (ui )| + |N (ui−1 ) ∩ N (x)| − |(N (ui−1 ) ∩ N (ui )) ∪ (N (ui−1 ) ∩ N (x))|
≥ |N (ui−1 ) ∩ N (ui )| + |N (ui−1 ) ∩ N (x)| − |N (ui−1 )|
≥ (1 − )∆ + (1 − 2)∆ − ∆ = (1 − 3)∆
Since x and ui are dense, we have |N (x) \ F (x)| ≤ ∆ and |N (ui ) \ F (ui )| ≤ ∆. Therefore,
|F (x) ∩ F (ui )| = |(N (x) ∩ N (ui )) \ (N (x) \ F (x)) \ (N (ui ) \ F (ui ))| ≥ (1 − 3)∆ − ∆ − ∆ ≥
(1 − 5)∆ > 0.
So x and ui have a common friend w, such that |N (x) ∩ N (w)| ≥ (1 − )∆ and |N (ui ) ∩ N (w)| ≥
(1 − )∆. So:
|N (x) ∩ N (ui )| ≥ |N (x) ∩ N (w) ∩ N (ui )|
= |N (w) ∩ N (ui )| + |N (w) ∩ N (x)| − |(N (w) ∩ N (ui )) ∪ (N (w) ∩ N (x))|
≥ |N (w) ∩ N (ui )| + |N (w) ∩ N (x)| − |N (w)|
≥ (1 − )∆ + (1 − )∆ − ∆ = (1 − 2)∆

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

7


Corollary 3.5. Suppose  < 1/5. Then all almost-cliques have weak diameter of at most 2.
Proof. By Lemma 3.4, any vertices x, y ∈ Cj have |N (x) ∩ N (y)| ≥ (1 − 2)∆ > 0. In particular,
they have a common neighbor.

A vertex v in Cj can identify all other members of Cj in O(1) rounds by the following procedure:
Initially, each vertex u ∈ G broadcasts the edges incident to u to all nodes within distance 3. In
this way, every vertex v learns the graph topology of all nodes up to distance 3, which is sufficient
to determine whether an edge (both of whose endpoints are within distance 2 of v) is a friend edge
and whether a vertex (within distance 2) is dense. Since by Corollary 3.5, all members of Cj are
within distance 2 to v, all the members can be identified. Also, the leader of Cj can be elected as
the member with the smallest ID.
Definition 3.6 (External degree). For any dense vertex v ∈ Cj , we define d(v), the external degree
of v, to be the number of dense neighbors of v outside Cj . (Sparse neighbors are not counted.)
Lemma 3.7. Any dense vertex v has d(v) ≤ ∆.
Proof. Let v ∈ Cj . As v is dense, it has at least (1 − )∆ friends. So it has at most ∆ dense
vertices which are not friends. If any dense vertex w is a friend of v, then by definition w ∈ Cj . So
v has at most ∆ dense neighbors outside Cj .

Definition 3.8 (Anti-degree). For any dense vertex v ∈ Cj , we define the anti-degree of v to be
a(v) = |Cj \ N (v)|.
Lemma 3.9. Suppose  < 1/5. Then any dense vertex v has a(v) ≤ 3∆.
Proof. Let v ∈ Cj , and let R denote the number of length-2 paths of the form v, x, u where x ∈ G
and u ∈ Cj \ N (v). We show this result by counting R into ways different ways. First, observe
that for any u ∈ Cj \ N (v), there are precisely |N (v) ∩ N (u)| possibilities for the middle vertex x.
Lemma 3.4 shows that:
X
X
R=
|N (v) ∩ N (u)| ≥
(1 − 2)∆ = a(v)(1 − 2)∆
u∈Cj \N (v)

u∈Cj \N (v)

We can also count R by summing over the middle vertex x:
X
X
R=
|N (x) ∩ (Cj \ N (v))| ≤
|N (x) \ N (v)|
x∈N (v)

=

X

x∈N (v)

|N (x) \ N (v)| +

x∈F (v)

≤

X

X

|N (x) \ N (v)|

x∈N (v)\F (v)

X

∆ +

x∈F (v)
2

∆

x∈N (v)\F (v)

≤ ∆ + (1 − )∆

(since v is dense, |F (v)| ≥ (1 − )∆)

2

= ∆ (2 − )
Combining these two inequalities gives a(v) ≤ ∆ (2−)
1−2 ; this is at most 3∆ for  < 1/5.



Corollary 3.10. For  < 1/5, all almost-cliques have size at most (1 + 3)∆.
Proof. Let v ∈ Cj . Then |Cj | = |Cj \ N (v)| + |Cj ∩ N (v)| ≤ a(v) + |N (v)| ≤ (1 + 3)∆.



8

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

4. Full algorithm outline
We can now describe our complete algorithm for list-coloring graphs, whether sparse or dense. It
will be convenient to have a “blank” color, which is available to all vertices and which we denote 0;
we say that χ(v) = 0 to indicate that v has not (yet) chosen a color. Our parameters will be
specified in terms of a constant K; we require K to be sufficiently large, and will state certain
conditions on its value later in the proofs. We assume that 4 ∆ ≥ K ln n. If 4 ∆ < K ln n,
then ∆ < polylog(n),
and so√that the coloring procedure of [8] will already color the graph in
√
log
log
n)
O(
= 2O( log log n) rounds.
O(log ∆) + 2
We set the density parameter to be
√

100− ln ∆
=
.
100K
Note that our assumptions ensure that  < 1/5, which is needed for the results of Section 3 and
elsewhere. The bound on  is used at a number of other places without further comment.
Algorithm 1 The coloring algorithm
1: Decompose G into V sparse , C1 , . . . , Ck .
2: Execute the initial coloring step:
3:
for all vertices v do
4:
v selects a tentative color A(v) as follows:
(
0,
with probability 99/100
A(v) =
color c ∈ Pal(v) chosen uniformly at random, with probability 1/100
5:
6:
7:
8:
9:
10:

if no neighbor w ∈ N (v) has A(w) = A(v) and A(v) 6= 0 then
v commits
√ to permanent color χ(v) = A(v).
for i = 1, . . . , d ln ∆e do
Execute the dense coloring step on the dense vertices (Algorithm 2)
Run the algorithm of [17] to color the sparse vertices.
Run the algorithm of [8] to color the residual graph.

The key subroutine for the coloring algorithm is the dense coloring step. The ith dense coloring
step is defined in terms of a parameter γi ∈ [0, 1], which we will specify shortly.
Algorithm 2 The dense coloring step
Initialize A(v) = 0 for all v ∈ V dense .
For each Cj , elect a leader `j to simulate the following process to color Cj :
Generate a random permutation
πj of Cj

4:
for k = 1, . . . , Lj = |Cj |γi do
5:
Vertex v = πj (k) selects A(v) uniformly at random from
1:
2:
3:

Pal(v) \ {A(πj (1)), . . . , A(πj (k − 1))}.
6:
7:
8:

for all Cj and all v ∈ Cj do
if no dense neighbor w ∈ N (v) has A(w) = A(v), where w ∈ Cj 0 and ID(`j 0 ) < ID(`j ) then
v commits to permanent color χ(v) = A(v).

We note that the decomposition of G in Line 1 of Algorithm 1 remains fixed for the entire
algorithm and all its dense coloring steps. Although in later steps vertices become colored and are
removed from G, we always define the decomposition in terms of the original graph G, not the

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

9

residual graph. However, we abuse notation so that when we refer to a component Cj during an
intermediate step, we mean the intersection of Cj with the residual (uncolored) vertices.
The algorithm is based on maintaining a partial coloring and a residual palette. That is, whenever
a vertex is colored, we remove it from the graph as well as the vertex sets V sparse , C1 , . . . , Ck ; also,
its selected color is removed from the palettes of its neighbors. An important parameter for such
partial-coloring algorithms is the difference between the available colors, i.e. the palette size Q(v)
and the uncolored neighbors d(v). We call this parameter (color) surplus S(v) of a vertex v, defined
by
S(v) = Q(v) − d(v)
The surplus S(v) is initially at least one for every vertex, since all palettes are of size ∆ + 1. A
vertex v can only lose a color from its palette if a neighbor becomes colored and drops out of the
residual graph. Therefore, S(v) can never decrease during the partial coloring.
For any vertex v, let Pal0 (v), d0 (v), S0 (v) denote, respectively, the palette, degree, and surplus
of v after the initial coloring step (note that the 0 in the subscript does not denote time 0, but
the time immediately after the initial coloring step). We set Q0 (v) = | Pal0 (v)|. We will show in
Theorem 5.6 that w.h.p. every sparse vertex v has S0 (v) = Ω(2 ∆) and that every vertex v (sparse
or dense) has Q0 (v) ≥ ∆/2.
Then we turn our attention to the dense vertices and we will show that they can be colored
efficiently. For a dense vertex x ∈ Cj , we let d0 (x) and a0 (x) denote its external degree and antidegree after the initial coloring step. Let Pali (x), di (x), di (x), ai (x), and Qi (x) denote the quantities
at the end of the ith dense coloring step. As we color the graph, we maintain two key parameters,
Di and Zi , which bound the external degree, anti-degree, and palette size for dense vertices after
the ith dense coloring step. Specifically, we ensure the invariant that every dense vertex v has
di (v) ≤ Di , ai (v) ≤ Di , Qi (v) ≥ Zi
We will then set our parameter γi by
p
γi = 1 − 2 Di−1 /Zi−1 ;
We will show in Corollary 7.3 that γi ∈ [0, 1] as required.
At the end of the dense coloring steps, every sparse vertex v has
Sd√ln ∆e (v) ≥ S0 (v) = Ω(2 ∆)
The algorithm of Elkin et al. [17] is designed for list-coloring where vertices have a large
surplus,
√
2
O(
log
log n) =
which indeed holds
for the sparse vertices. Thus they can be colored in O(log(1/ ))+2
√
√
O(
log
log
n)
O( log ∆) + 2
rounds. This removes the sparse vertices from the graph, leaving only
the dense vertices behind.
After the sparse vertices are removed,
Theorem 7.6 shows that each remaining dense vertex is
√
0 = O(log n) · 2O( log ∆) other vertices. The algorithm of [8] then takes O(log ∆0 ) +
connected
to
∆
√
√
√
2O( log log n) = O( log ∆) + 2O( log log n) steps.
5. The initial coloring step
The initial coloring step is designed to achieve two important objectives:
(A1) For every vertex v, we have Q0 (v) ≥ ∆/2.
(A2) For every sparse vertex v, we have S0 (v) = Ω(2 ∆).
Recall that Q0 and d0 are respectively the palette size and degree of vertex v after the initial coloring
step, and the (color) surplus is S0 (v) = Q0 (v) − d0 (v). Property (A1) is fairly straightforward, and
most of our effort will be to show that (A2) holds w.h.p. for a given sparse vertex v.

10

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

1
We briefly summarize the initial coloring step. With probability α = 100
, each vertex v chooses
1
a tentative color A(v) uniformly at random from its palette. It discards the tentative color if any
neighbor also chooses the same tentative color; in this case we say that v is de-colored. We let χ(v)
denote the permanent color selected by v after the initial coloring step. We say that A(v) = 0 if
vertex v chose not to select a color initially and we say χ(v) = 0 if v is uncolored (either because
it did not select a tentative color, or it became de-colored).
For each color c and each vertex v, we define Nc (v) to be the set of neighbors of v whose palette
contains c; that is,
Nc (v) = {w ∈ N (v) | c ∈ Pal(w)}
Let us now fix some sparse vertex v, and show that after the initial coloring step v has a large
surplus. We define a color c to be good if
X
[χ(w) = c] ≥ 1 + [c ∈ Pal(v)]
w∈N (v)

(Here and in the remainder of the paper, we use the Iverson notation so that for any predicate P,
[P] is equal to 1 if P is true and zero otherwise.)
Let J denote the set of colors that are good for v.
Proposition 5.1. The following bound holds with probability one:
S0 (v) ≥ |J|
Proof. Suppose c ∈
/ Pal(v) and there is some neighbor w ∈ N (v) with χ(w) = c. When we remove w
from the residual graph, Pal(v) does not change while d(v) decreases by one. Suppose c ∈ Pal(v),
and there are two neighbors w1 , w2 ∈ N (v) with χ(w1 ) = χ(w2 ) = c. When we remove w1 and w2
from the residual graph, Pal(v) decreases by one while d(v) decreases by two.

In light of Proposition 5.1, it will suffice to show that |J| is large with high probability. We do
so in two stages: first, we show that E[|J|] is large, and second we show that |J| is concentrated
around its mean.

Lemma 5.2. For c ∈
/ Pal(v), we have P (c ∈ J) = Ω |Nc (v)|/∆ .
Proof. For each x ∈ Nc (v), let us define Bx to be the event that (i) A(x) = c and (ii) A(z) 6= c for
all z ∈ N (v) ∪ N (x) \ {x}.
If event Bx occurs, then we will have χ(x) = c, and so c will go into J. Also, condition (ii)
ensures that the events Bx are all mutually exclusive. Thus
_
X
P (c ∈ J) ≥ P (
Bx ) =
P (Bx )
x∈Nc (v)

=

X
x∈Nc (v)

≥

x∈Nc (v)

α
α |Nc (x)∪Nc (v)\{x}|
1−
≥
∆+1
∆+1

|Nc (v)|α(1 −
∆



α)2

= Ω |Nc (v)|/∆

X
x∈Nc (v)

α 
α 2∆−1
1−
∆+1
∆+1




Lemma 5.3. Suppose that ∆ ≥ 3. If c ∈ Pal(v) and |Nc (v)| ≥ (1 − /2)∆, then P (c ∈ J) = Ω(2 ).
Proof. Define U to be the set of ordered pairs (x, y) with x, y ∈ Nc (v), x < y and xy ∈
/ E. For
every pair of vertices (x, y) ∈ U , let us define Bx,y to be the event that (i) A(x) = A(y) = c and
(ii) A(z) 6= c for all z ∈ N (v) ∪ N (x) ∪ N (y) \ {x, y}.
1We will write α instead of directly writing 1/100.

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

11

If event Bx,y occurs, then (as x, y are not neighbors) we will have χ(x) = χ(y) = c, and so c will
go into J. Also, note that condition (ii) ensures that the events Bx,y are mutually exclusive. Thus,
X
_
P (Bx,y )
Bx,y ) =
P (c ∈ J) ≥ P (
(x,y)∈U

(x,y)∈U

=

α2

X
(x,y)∈U

≥

X
(x,y)∈U

(∆ +

1)2

1−

α |Nc (v)∪Nc (x)∪Nc (y)\{x,y}|
∆+1

X
α2
α 3∆−2
α2
|U |
1
−
(1 − α)3 = Ω( 2 )
≥
2
2
(∆ + 1)
∆+1
(∆ + 1)
∆
(x,y)∈U

Next, we estimate |U |. Consider the set W = {w ∈ Nc (v) | wv ∈
/ F }. By definition of sparsity,
v has at most (1 − )∆ friends. Thus, |W | ≥ |Nc (v)| − (1 − )∆ ≥ ∆/2.
Since each w ∈ W is not a friend of v, we have |N (w) ∩ N (v)| < (1 − )∆. So |Nc (v) \ (N (w) ∪
{w})| ≥ |Nc (v)| − 1 − |N (v) ∩ N (w)| > ∆/2 − 1. So we count U as follows:
X
X
X
1
1
|U | =
1=
≥
2
2
x∈Nc (v)
y∈Nc (v)\N (x)
y<x

≥

1
2

X

x∈W
x∈Nc (v)
y∈Nc (v)\(N (x)∪{x}) y∈Nc (v)\(N (x)∪{x})

(∆/2 − 1) ≥

x∈W
2 2

· (/2)∆ · (∆/2 − 1)

(as ∆ ≥ 3 and  < 1/5)

= Ω( ∆ )
2

1
2

2

This shows that P (c ∈ J) = Ω(  ∆∆2 ) = Ω(2 ).



Lemma 5.4. Suppose that ∆ ≥ 3. If d(v) ≥ (1 − /4)∆, then E[|J|] = Ω(2 ∆).
Proof. Let us partition the set of colors C into three disjoint sets:
B1 = {c ∈ C | c ∈
/ Pal(v)}
B2 = {c ∈ C | c ∈ Pal(v), |Nc (v)| ≥ (1 − /2)∆}
B3 = {c ∈ C | c ∈ Pal(v), |Nc (v)| < (1 − /2)∆}
If |B2 | ≥ ∆/4, then by Proposition 5.3 we immediately have
X
E[|J|] ≥
P (c ∈ J) ≥ ∆/4 · Ω(2 )
c∈B2

and we are done. So let us suppose that |B2 | < ∆/4.
Recall that | Pal(w)| = ∆ + 1 for every vertex w. Thus, for each w ∈ N (v), there are exactly
∆ + 1 values of c with w ∈ Nc (v). By double counting,
X
X
X
X
(∆ + 1)d(v) =
|Nc (v)| =
|Nc (v)| +
|Nc (v)| +
|Nc (v)|
c∈C

≤

X

c∈B1

c∈B2

c∈B3

|Nc (v)| + |B2 |∆ + |B3 |(1 − /2)∆

c∈B1

Rearranging, and using the fact that | Pal(v)| = |B2 | + |B3 | = ∆ + 1, gives:
X
|Nc (v)| ≥ (∆ + 1)d(v) − |B2 |∆ − |B3 |(1 − /2)∆
c∈B1

≥ (∆ + 1)(1 − /4)∆ − |B2 |∆ − (∆ + 1 − |B2 |)(1 − /2)∆
=

∆
4 (∆

+ 1 − 2|B2 |) ≥ ∆2 /16

12

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

where the last inequality holds since |B2 | < ∆/4.
Lemma 5.2 then gives:
X
X
P (c ∈ J) ≥
Ω(|Nc (v)|/∆) = Ω(2 ∆).
E[|J|] ≥
c∈B1

c∈C\Pal(v)


Lemma 5.5. With probability at least 1 − e

−Ω(4 ∆)

, we have S0 (v) = Ω(2 ∆).

Proof. If d(v) ≤ 1 − ∆/4 then S0 (v) ≥ ∆/4 = Ω(2 ∆) with certainty. Also, if ∆ < 3, then
S0 (v) ≥ 1 = Ω(2 ∆) with certainty. So let us assume that d(v) > 1 − ∆/4 and ∆ > 3. We will
4
now show |J| = Ω(2 ∆) with probability at least 1 − e−Ω( ∆) . By Proposition 5.1 this will establish
the result.
Let W = {v} ∪ N (v) and let U denote the set of vertices with distance 2 to v. Let us define J 0
to be the set of colors which would be good if A(x) = 0 for all x ∈ U . Note that vertices in U can
de-color vertices in W . So vertices of U can only remove colors from J and hence J ⊆ J 0 .
Since J ⊆ J 0 , Proposition 5.4 shows that
E[|J 0 |] ≥ φ2 ∆
for some constant φ > 0.
Note that for w ∈ W , modifying the value of A(w) can only change |J 0 | by at most 2 (the value
of A(w) only affects whether A(w) ∈ J 0 ). Hence, by the Bounded Differences Inequality,
!

φ2 ∆ 
(φ2 ∆)2
0
P |J | <
≤ exp − P
≤ exp(−Ω(4 ∆))
2
2 · i∈{v}∪N (v) 22
Now, let us condition on the full set of values A(w) for w ∈ W , and also condition on the event
≥ φ2 2 ∆ (which only depends on the values of A(w) for w ∈ W ). Let j = |J 0 |. The values
of A(u) for u ∈ U are still independent and uniform, and each such vertex has the possibility of
de-coloring a vertex in W .
For each c ∈ J 0 \ Pal(v), let yc be any vertex in N (v) with A(yc ) = c and not de-colored by
any vertices in W . Similarly, for c ∈ J 0 ∩ Pal(v), let yc , yc0 be any two vertices in N (v) with
A(yc ) = A(yc0 ) = c and not de-colored by any vertices in W (so yc and yc0 cannot be neighbors).
Such colors will go into J unless a vertex in N (yc ) selects c (respectively, in N (yc ) ∪ N (yc0 ) selects
color c.)
If a vertex u ∈ U selects A(u) = c for such a color c ∈ J 0 , causing color c to not appear in J, we
say that u disqualifies color c. Define the random variable R by
X
R=
[u disqualifies color c]
|J 0 |

c∈J 0
u∈(N (yc )∪N (yc0 ))∩U

Observe that |J| ≥ |J 0 | − R = j − R, and so the Lemma will follow by showing that R < j/2.
α
. Furthermore
Each vertex u ∈ U disqualifies any given color c with probability at most ∆+1
0
there are at most 2∆ vertices u ∈ U that can disqualify any given color c ∈ J . Hence,
X
α
E[R] ≤
P (u disqualifies color c) ≤ j · 2∆ ·
∆+1
0
c∈J
u∈(N (yc )∪N (yc0 ))∩U

≤ j/4

as α = 1/100

All such disqualification events are negatively correlated. Using the fact that j ≥
Chernoff’s bound to obtain
φ2 ∆
P (R ≥ j/2) ≤ e−(j/4)·4/3 ≤ exp(−
) ≤ exp(−Ω(2 ∆))
6

φ2 ∆
2 ,

we apply

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

Overall, we have shown that |J| = Ω(2 ∆) with probability 1 − exp(−Ω(4 ∆)).

13



Theorem 5.6. For K a sufficiently large constant, properties (A1) and (A2) hold for every vertex
w.h.p.
Proof. By Lemma 5.5, for any individual sparse vertex v the probability that (1) fails is at
4
0
most e−Ω( ∆) . Since 4 ∆ ≥ K ln n, this is at most n−K for an arbitrary large constant K 0 > 0
given that K is sufficiently large. (A2) follows by taking a union bound over all sparse vertices.
To show property (A1), fix some vertex v, and note that any w ∈ N (v) chooses an initial color
with probability at most α, independently of any other vertices. Thus, a Chernoff bound shows that
there is a probability of e−Ω(∆) that more than ∆/2 neighbors of v are colored. So with probability
1 − e−Ω(∆) , vertex v loses at most ∆/2 colors from its original palette of size of ∆ + 1. Again, this
0
is at most n−K for an arbitrary constant K 0 > 0 given that K is sufficiently large.

6. Coloring the dense vertices
Suppose that we are at the beginning of the ith dense coloring step. We assume that there are
parameters Di−1 , Zi−1 , such that all dense vertices v have the following properties:
(1) ai−1 (v) ≤ Di−1
(2) d¯i−1 (v) ≤ Di−1
(3) Qi−1 (v) ≥ Zi−1
¯
Henceforth we will suppress the √
dependence on i and write D, Z, a(v), d(v),
Pal(v), and Q(v).
We define δ = D/Z and γ = (1 − 2 δ).
Let us consider some almost-clique Cj , with Mj = |Cj | vertices. The dense coloring step for each
Cj generates a permutation πj of its members. Starting from vertex πj (1) up to vertex πj (Lj ), where
Lj = dMj γe, each vertex selects a tentative color from its palette excluding the colors selected by
lower rank vertices. (Note that the leader `j in Cj simulates this process.) Then, a vertex becomes
de-colored if an external neighbor from a lower indexed component chooses the same color.
Our goal is to show for some parameters D0 and Z 0 that at the end of the round holds ai (v) ≤
0
D , di (v) ≤ D0 and Qi (v) ≥ Z 0 . To do this, we will show that most vertices are colored in round i.
We require throughout this section the following conditions on D and Z, which we will refer to
as the regularity conditions:
(R1) Dδ ≥ K ln n for some sufficiently large constant K
(R2) δ ≤ 1/K for some sufficiently large constant K
Recall that K is a universal constant that we will not explicitly compute. At several places we will
assume it is sufficiently large. In Section 7 we will discuss how to satisfy these regularity conditions
(or how our algorithm can succeed when they become false). In Section 6, we require implicitly
that these regularity conditions all hold.
6.1. Overview. We first contrast our dense coloring procedure with a naive one, which assigns
each vertex a random color and de-colors a vertex if there is a conflict. It is not hard to show that
such a procedure successfully assigns a color to a vertex with constant probability. Thus, in each
round, the degrees are shrinking by a constant factor in expectation. So it takes Ω(log ∆) rounds
to reduce to a low (near-constant) degree.
In order to get a faster algorithm, we need to color much more than a constant fraction of
all vertices per round. Here, the network decomposition plays the decisive role as only external
neighbors of a vertex v can de-color v. To illustrate, suppose that each vertex v selects a color
from its palette uniformly at random. (That is, suppose we ignore the interaction between v and
the other vertices in Cj ). Since the external neighbors are upper bounded by D and the palette
size is at least Z, even if the external neighbors of v choose distinct colors, the probability that v
has any conflicts with its neighbors is upper bounded by D/Z = δ = O(). Ideally, we would like

14

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

to show that each cluster shrinks by a factor of δ in each round. Moreover, one would also need to
prove that the ratio D0 /Z 0 in the next round remains approximately δ, so that the almost-cliques
continue to shrink by the same factor.
The reason why we only attempt to color the first Lj vertices rather than the entire almost-clique
is that we cannot afford the palette size to shrink too fast. A “controlled” uniform shrinking process
maintains the overall ratio between palette size, external neighbors, and internal neighbors. This
renders undesirable scenarios very unlikely.
The following lemma uses the regularity conditions to show a useful bound on several parameters
of the almost-clique.
Lemma 6.1. For any v ∈ Cj , the following bound holds with probability one:
√
Q(v) − Lj ≥ Z δ + D
Proof. Note that Mj = |N (v) ∩ Cj | + |Cj \ N (v)| ≤ d(v) + a(v) ≤ Q(v) + D. Therefore,
√
Q(v) − Lj ≥ Q(v) − dM γe ≥ Q(v) − Mj (1 − 2 δ) − 1
√
≥ Q(v) − (Q(v) + D)(1 − 2 δ) − 1
√
√
= 2Q(v) δ + 2D δ − D − 1
√
√
≥ 2Z δ + 2D δ − D − 1
as Q(v) ≥ Z
√
√
√
as D = δZ by definition
= Z δ + D/ δ + 2D δ − D − 1
√
≥Z δ+D
as (1/δ) ≥ K and D ≥ 2 by regularity conditions

6.2. Concentration of the number of uncolored vertices. We will show that most vertices
become colored at the end of a dense coloring step. We distinguish two ways in which a vertex v
could fail to be colored: first, it may be de-colored in the sense that it initially chose a color, but
then had a conflict with an almost-clique of smaller index. Second, it may be initially-uncolored in
the sense that πj−1 (v) > Lj .
Lemma 6.2. Let T = {v1 , . . . , vt } ⊆ Cj . Let c1 , . . . , ct be an arbitrary sequence of non-blank colors.
Then
√
P (A(v1 ) = c1 ∧ · · · ∧ A(vt ) = ct ) ≤ (Z δ)−t
Proof. Let us condition on the permutation πj , and without of loss generality πj−1 (v1 ) < πj−1 (v2 ) <
· · · < πj−1 (vt ). We assume πj−1 (vt ) ≤ Lj as otherwise A(vt ) = 0.
For each i = 1, . . . , t we claim that P (A(vi ) = ci ) ≤ Q(vi1)−Lj , even after conditioning on all the
colors choices made by vertices w with πj−1 (w) < πj−1 (vi ). For, at this point, at most πj−1 (vi ) ≤ Lj
colors from the palette of vi have been used by previously-colored neighbors from Cj . Hence, vi
has a remaining palette of size Q(vi ) − Lj . Using Lemma 6.1 then gives
P (A(vi ) = ci | A(v1 ) = c1 ∧ · · · ∧ A(vi−1 ) = ci−1 ) ≤

1
1
≤ √
Q(vi ) − Lj
Z δ


Lemma
Let T ⊆ V dense . The probability that all the vertices in T become de-colored is at
√ 6.3.
|T
|
most ( δ) .
Proof. Let us sort the almost-cliques C1 , . . . , Ck by the vertex ID of their leaders, so that `1 ≤
`2 ≤ . . . ≤ `k . For each j = 1, . . . , k we define Tj = T ∩ Cj .

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

15

show for any j that the vertices in Tj become de-colored with probability at most
√We|T will
|
j
( δ) , conditioned on the event that the vertices in T1 , . . . , Tj−1 become de-colored. In fact, we
will not just condition on the event that the vertices in T1 , . . . , Tj−1 become de-colored, but we will
condition on the complete set of random variables involved in C1 , . . . , Cj−1 . (The event that Tj
becomes de-colored is a function of only the colors involved in C1 , . . . , Cj .)
¯ ≤ D events of the
For each v ∈ Tj , the event that v becomes de-colored is a union of at most d(v)
form χ(v) = c, where c enumerates the colors selected by vertices in N (v) ∩ (C1 ∪ C2 ∪ · · · ∪ Cj−1 ).
|Tj | events of
Hence, the event that all of the vertices in Tj become de-colored is a union
√ −|Tof| D
the form stated in Lemma 6.2, each of which has probability at
(Z δ) j . Therefore, the
√ most
D
|T
|
|T
|
probability that all of them become de-colored is ( Z √δ ) j = ( δ) j .

Lemma 6.4.
Let T ⊆ V dense . The probability that all of the vertices in T are initially uncolored is
√ |T
at most (2 δ) | .
Proof. It suffices to show that for a particular
Cj , the probability that all vertices in Tj = T ∩ Cj
√
are initially uncolored is bounded by (2 δ)|Tj | , since the nodes in distinct almost-cliques make their
choices independently.
We select from Cj a set of Lj vertices to be colored, uniformly at random without replacement.
Thus, the probability that all vertices in Tj are initially-uncolored is:
Mj −|Tj |
P (Tj is initially uncolored) =

Lj
Mj 
Lj

If |Tj | > Mj − Lj , the right hand side is zero and we are done. Otherwise,
 M − |T |  M − |T | − 1 
 M − L + 1 − |T | 
j
j
j
j
j
j
j
P (Tj is initially uncolored) =
...
Mj
Mj − 1
Mj − Lj + 1
 M − 1 |Tj |  M − 2 |Tj |
 M − L + 1 − 1 |Tj |
j
j
j
j
≤
...
Mj
Mj − 1
Mj − Lj + 1
√ 



√
Lj |Tj |
Mj (1 − 2 δ) |Tj |
= 1−
≤ 1−
= (2 δ)|Tj |
Mj
Mj

Lemma 6.5. Let T ⊆ V

dense ,

K√ln n
.
δ

and let s be a real number with s ≥ |T |, s ≥
Then the
√
0
probability that T contains more than 12s δ uncolored vertices at the end of round i is at most n−K
for an arbitrarily large constant K 0 > 0.
√
Proof. Let x = 6s δ. We claim that the number of de-colored vertices in T is at most x with
0
probability 1 − n−K /2 and we also claim that the number of initially-uncolored vertices is at most
0
x with probability 1 − n−K /2; combining these two claims gives the stated result.
The proofs are nearly the same, so we show only the latter one. By a union bound over all
possible sets of size dxe, the probability that the number of initially-uncolored vertices exceeds dxe
is at most
 
 e|T | dxe
√
√
|T |
(2 δ)dxe ≤
· (2 δ)dxe
dxe
dxe
 es(2√δ) x
√
√
≤
as x = 6s δ and |T | ≤ s
6s δ
 2e K ln n
√
≤
as x ≥ 6s δ ≥ K ln n
6
0
≤ n−K /2
for K a sufficiently large constant.

16

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU


Lemma 6.6. W.h.p. at the end of round i, every dense vertex v satisfies the bounds
ai (v) ≤ D0 ,
for the parameters

di (v) ≤ D0 ,

√
D0 = 12D δ

Qi (v) ≥ Z 0

√
Z 0 = D/ δ

Proof. Let v ∈ Cj . We first note that the regularity conditions imply Dδ ≥ K ln n and hence
D ≥ K√lnδ n .
So we may apply Lemma 6.5 with T being the set of external neighbors of v and s = D to
0
show that that di (v) ≤ D0 holds with probability at least 1 − n−K for an arbitrarily large constant
K 0 > 0. Similarly, we apply Lemma 6.5 with T = Cj \N (v) and s = D to show that that ai (v) ≤ D0
0
holds with probability ≥ 1 − n−K .
Next, we bound Qi (v). We color at most D external neighbors and at most Lj internal neighbors.
√
Thus, the residual palette of v has size at least Qi (v)−Lj −D. By Lemma 6.1, this is at least D/ δ
for K sufficiently large.
Finally, take a union bound over all dense vertices v.

Proposition 6.7. W.h.p. at the end of round i, every almost-clique Cj has size at most
√
max(12K ln n, 12Mj δ)
Proof. Apply Lemma 6.5 with T = Cj and s = max(Mj , K√lnδ n ); this shows that with probability at
√
0
least 1 − n−K for an arbitrarily large constant K 0 > 0 there are at most max(12K ln n, 12Mj δ)
uncolored vertices remaining in Cj . Finally, take a union bound over all almost-cliques Cj .

7. Solving the recurrence
In light of Lemma 6.6, we can explicitly derive a recurrence relation for the parameters Di and Zi .
We define δi = Di /Zi throughout.
Lemma 7.1. Define the recurrence relation with initial conditions
D0 = 3∆

Z0 = ∆/2

and recurrence
Di+1 = 12Di

p

δi

p
Zi+1 = Di / δi

√
Let i ≤ d ln ∆e. Assuming that the regularity conditions (R1), (R2) are satisfied for j =
0, . . . , i − 1, then we have w.h.p.:
ai (v) ≤ Di , di (v) ≤ Di , Qi (v) ≥ Zi
Proof. The bound on Z0 is given in Theorem 5.6. By Lemma 3.7 and Lemma 3.9, we get a(v) ≤ 3∆
and d(v) ≤ 3∆ in the initial graph. The initial coloring step cannot increase these parameters, so
we have a0 (v) ≤ 3∆, d0 (v) ≤ 3∆ as well. This shows the bound on D0 .
A simple induction, using Lemma 6.6, shows that for all i = 1, . . . , n we have the following:
0

ai (v) ≤ Di , di (v) ≤ Di , Qi (v) ≥ Zi
with probability 1 − n−K
√
Thus, for
i ≤ d ln ∆e, the probability that any of these events does not occur, is at
√ any fixed
0
0
most (1 + ln ∆)n−K ≤ n−K +1 for an arbitrarily large constant K 0 > 0.

We will now show how to solve this recurrence.
√
Lemma 7.2. For all i ≤ d ln ∆e we have δi = 6 · 12i ≤ 1/K.

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

17

Proof. For each i > 0, we may compute δi as
p
12Di−1 δi−1
Di
p
=
= 12δi−1
δi =
Zi
Di−1 / δi−1
As√δ0 = D0 /Z0 = 6, we have δi = 6 · 12i as claimed. Now, recalling our formula  =
100− ln ∆ /(100K), we have
√

√
√
√
100− ln ∆ 
72
δi ≤ 6
· 12 ln ∆+1 ≤
100− ln ∆ 12 ln ∆ ≤ 1/K.
100K
100K



√
Corollary 7.3. For every i ≤ d ln ∆e, we have γi ∈ [0, 1].
p
Proof. Follows immediately from Lemma 7.2 and the definition γi = 1 − 2 δi−1 .
√
√
2
Lemma 7.4. For all 5 ≤ i ≤ d ln ∆e, we have Di ≤ 12i /2 · 10−i ln ∆ · ∆.



Proof. We recursively compute Di from D0 as:
Di = D0 ·

(1)

i−1
Y

p
12 δj

j=0

Using Lemma 7.2 we then estimate:
Di ≤ 3∆

i−1
Y

1/2

12δj

j=0



≤ ∆ · 12i
≤ ∆ · 12

i2 /2

6·

≤ 3∆

i−1 
Y

j=0
√
ln
∆
−
i/2
100

100K
√
· 10−i ln ∆




12(6 · 12j )1/2 = (3∆) · 12i (6)i/2 · 12i(i−1)/4

√
· 12i(i−1)/4 ≤ ∆ · 12i(i+5)/4 · 100−i ln ∆/2

as (i + 5)/4 ≤ i/2 for i ≥ 5


Corollary 7.5. We have the bound Dd√ln ∆e = O(1).
√
Proof. If ln ∆ ≤ 5, then Di ≤ D0 = 3∆ = O(1). Otherwise, we apply Lemma 7.4:
√
√
√
√
√
2
2
Dd√ln ∆e ≤ ∆ · 12d ln ∆e /2 · 10− ln ∆d ln ∆e ≤ ∆ · ( 12)( ln ∆+1) · 10− ln ∆ = O(1)

Theorem 7.6. At √the end of the dense coloring steps, w.h.p. every dense vertex is connected to at
most O(log n) · 2O( log ∆) other dense vertices.
√
Proof. Let i∗ ≤ d ln ∆e be minimal such that Di∗ δi∗ ≤ K ln n; Corollary 7.5 ensures such an i∗
exists.
√
The regularity conditions are satisfied up to round i∗ . Noting that δi∗ ≥  = 2−Θ( log ∆) ,
Lemma 7.1 shows that:
√

(2)

di∗ (v) ≤ Di∗ ≤ (K ln n)/δi∗ = O(log n) · 2O(

log ∆)

Next, we bound the size of each almost-clique Cj . The initial size of Cj is at most (1 + 3)∆.
Applying Proposition 6.7 repeatedly for i < i∗ shows that the size of Cj reduces to
max(12K ln n, (1 + 3)∆ ·

∗ −1
iY

i=0

p
12 δi )

18

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

w.h.p. We bound the latter term as follows:
(1 + 3)∆ ·

∗ −1
iY

i=0

p
Di∗
12 δj = (1 + 3)∆ ·
3∆

by (1) and D0 = 3∆

(1 + 3)K ln n O(√log ∆)
·2
by (2)
3
√
√
= O(log n) · 2O( log ∆)
as 1/2Θ( log ∆)

≤

√

√

We have shown that v ∈ Cj has O(log n) · 2O( log ∆) external neighbors and O(log n) · 2O( log ∆)
neighbors w ∈ Cj after round
i∗ . Dense coloring steps after round i∗ can only decrease the degree
√
√
of v, so v has O(log n) · 2O( log ∆) dense neighbors after round d ln ∆e.

8. List-coloring locally-sparse graphs
Although the √overall focus of this paper is an algorithm for coloring arbitrary graphs in time
√
O( log ∆) + 2O( log log n) , we note that our initial coloring step may also be used to obtain a faster
list-coloring algorithm for sparse graphs. This result extends the work of [17], which showed a
similar type of (∆ + 1)-coloring algorithm for graphs which satisfy a property they refer to as local
sparsity. We define this property and show that it is essentially equivalent to the definition of
sparsity defined in Section 3.

Definition 8.1. A graph G is (1 − δ)-locally sparse if very vertex contains at most (1 − δ) ∆
2 edges
in its neighborhood,
for some parameter δ ∈ [0, 1]. (That is, the induced subgraph G[N (v)] contains

edges).
≤ (1 − δ) ∆
2
Lemma 8.2. Suppose that G is (1 − δ)-locally sparse. If we apply the network decomposition of
Section 3 with parameter  = δ/2, then every vertex is sparse, i.e. V sparse = V .
Proof. Suppose that v ∈ V is dense with respect to . Then v has at least (1 − )∆ friends. Each
such friend u corresponds to at least (1 − )∆ edges between u and another neighbor of v, that is,
an edge in G[N (v)]. Furthermore, any such
edge in G[N (v)] is counted at most twice, so G[N (v)]

must contain (1 − )2 ∆2 /2 ≥ (1 − 2) ∆
edges,
which contradicts our hypothesis for  ≥ δ/2. 
2
Corollary 8.3. Suppose that G is (1 − δ)-locally-sparse and that every
vertex has a palette of size
√
O(
log
log n) rounds.
exactly ∆ + 1. Then G can be list-colored w.h.p. in O(log(1/δ)) + 2
Proof. By Proposition 8.2, every vertex in G is sparse with respect to parameter  = δ/2.
First suppose that δ 4 ∆ ≥ K ln n, where K is a sufficiently large constant. Then by Theorem 5.6,
each vertex satisfies S0 (v) √= Ω(2 ∆) w.h.p. The algorithm of [17] applied to the residual graph
runs in O(log(1/δ 2 )) + 2O( log log n) rounds.
Next,
suppose that δ 4 ∆ ≤ K
ln n. Then the coloring algorithm of [8] runs in O(log ∆) +
√
√
O(
log
log
n)
O(
log
log n) rounds.
2
= O(log(1/δ)) + 2

9. Conclusions
Distributed symmetry breaking tasks such as coloring or MIS lie at the heart of distributed
computing. We have shown that the (∆ + 1)-coloring problem is easier than MIS. However, there
is still a large gap in the round √complexity between the best lower bound of Ω(log∗ n) and our
√
upper bound of O( log ∆) + 2O( log log n) . Recent advances for lower bounds [9, 12, 28, 10] for the
LOCAL model and its variants might yield inspiration for improving the existing lower bound. Our
deterministic decomposition into locally sparse and dense parts might foster additional advances
as well. It might help to further reduce upper bounds for symmetry breaking tasks – in particular

DISTRIBUTED (∆ + 1)-COLORING IN SUBLOGARITHMIC ROUNDS1

19

for deterministic algorithms, since there exist efficient algorithms for (very) dense graphs, e.g. [51],
and sparse graphs, e.g. [22]. Furthermore, the
gap for (∆ + 1)-coloring between our randomized
√
√
log
log n) and the best deterministic algorithm requirO(
algorithm
in time O( log ∆) + 2
√ running
2.5
∗
ing O( ∆ log ∆ + log n) [20] is more than exponential and, therefore, larger than any known
separation result for randomized and deterministic algorithms [11].
Acknowledgments: We would like to thank Seth Pettie for his valuable comments. We thank
the anonymous reviewers for many helpful suggestions and comments.

References
[1] N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent
set problem. Journal of Algorithms, 7(4):567–583, 1986.
[2] B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed
computation. In Proc. of Symp. Foundations of Computer Science (FOCS), 1989.
[3] L. Barenboim. Deterministic (∆ + 1)-coloring in sublinear (in ∆) time in static, dynamic and faulty networks.
In Symp. on Principles of Distributed Computing(PODC), pages 345–354, 2015.
[4] L. Barenboim and M. Elkin. Deterministic distributed vertex coloring in polylogarithmic time. Journal of the
ACM (JACM), 58(5):23, 2011.
[5] L. Barenboim and M. Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis
Lectures on Distributed Computing Theory, 4(1):1–171, 2013.
[6] L. Barenboim, M. Elkin, and C. Gavoille. A fast network-decomposition algorithm and its applications to
constant-time distributed computation. Journal of Theoretical Computer Science, 2016.
[7] L. Barenboim, M. Elkin, and F. Kuhn. Distributed (∆ + 1)-coloring in linear (in ∆) time. SIAM Journal on
Computing, 43(1):72–95, 2014.
[8] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. Journal of
the ACM (JACM), 63, 2016. Article 20.
[9] S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto. A lower
bound for the distributed Lovász local lemma. In Proc. of Symposium on Theory of Computing (STOC), pages
479–488, 2016.
[10] Y.-J. Chang, Q. He, W. Li, S. Pettie, and J. Uitto. The complexity of distributed edge coloring with small
palettes. In arXiv preprint arXiv:1708.04290, 2017.
[11] Y.-J. Chang, T. Kopelowitz, and S. Pettie. An exponential separation between randomized and deterministic
complexity in the local model. In Proc. of Foundations of Computer Science (FOCS), pages 615–624. IEEE,
2016.
[12] Y.-J. Chang and S. Pettie. A time hierarchy theorem for the LOCAL model. In Proc. of Symp. on Foundations
of Computer Science (FOCS), 2017.
[13] I. Chlamtac and S. Kutten. A spatial reuse TDMA/FDMA for mobile multi-hop radio networks. In Proc. of the
Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Technology: Emerging or
Converging, pages 389–394 vol.1, 1985.
[14] K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász local lemma and graph coloring.
Journal of Distributed Computing, 30(4):261–280, 2017.
[15] I. Cidon and M. Sidi. Distributed assignment algorithms for multihop packet radio networks. IEEE Transactions
on Computers, 38(10):1353–1361, 1989.
[16] D. Dubhashi, D. A. Grable, and A. Panconesi. Near-optimal, distributed edge colouring via the nibble method.
Journal of Theoretical Computer Science (TCS), 203(2):225–251, Aug. 1998.
[17] M. Elkin, S. Pettie, and H.-H. Su. (2∆−1)-edge-coloring is much easier than maximal matching in the distributed
setting. In Symp. on Discrete Algorithms (SODA), pages 355–370. SIAM, 2015.
[18] A. Ephremides and T. V. Truong. Scheduling broadcasts in multihop radio networks. IEEE Transactions on
Communications, 38(4):456–460, 1990.
[19] M. Fischer and M. Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma with implications on
complexity hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC), page 18,
2017.
[20] P. Fraigniaud, M. Heinrich, and A. Kosowski. Local conflict coloring. In Proc. of Foundations of Computer
Science (FOCS), pages 625–634. IEEE, 2016.
[21] M. Ghaffari. An improved distributed algorithm for maximal independent set. In Proc. 27th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA), pages 270–277, 2016.

20

DAVID G. HARRIS AND JOHANNES SCHNEIDER AND HSIN-HAO SU

[22] M. Ghaffari and C. Lymouri. Simple and near-optimal distributed coloring for sparse graphs. In arXiv preprint
arXiv:1708.06275, 2017.
[23] A. V. Goldberg and S. A. Plotkin. Parallel (∆ + 1)-coloring of constant-degree graphs. Information Processing
Letters, 25(4):241 – 245, 1987.
[24] A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM J.
Discrete Math., 1(4):434–446, 1988.
[25] M. Göös, J. Hirvonen, and J. Suomela. Linear-in-∆ lower bounds in the local model. In Proc. of Symposium on
Principles of Distributed Computing(PODC), pages 86–95, 2014.
[26] D. A. Grable and A. Panconesi. Nearly optimal distributed edge coloring in O(log log n) rounds. Journal of
Random Structures & Algorithms, 10(3):385–405, 1997.
[27] D. A. Grable and A. Panconesi. Fast distributed algorithms for Brooks–Vizing colorings. Journal of Algorithms,
37(1):85 – 120, 2000.
[28] D. Hefetz, F. Kuhn, Y. Maus, and A. Steger. Polynomial lower bound for distributed graph coloring in a weak
local model. In Proc. of International Symposium on Distributed Computing(DISC), pages 99–113. Springer,
2016.
[29] J. Hirvonen and J. Suomela. Distributed maximal matching: Greedy is optimal. In Proc. of Symp. on Principles
of Distributed Computing(PODC), pages 165–174, 2012.
[30] Ö. Johansson. Simple distributed ∆ + 1-coloring of graphs. Inf. Process. Lett., 70, 1999.
√
[31] K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. Distributed coloring in Õ( log n) bit rounds. In
Proc. of International Parallel and Distributed Processing Symposium (IPDPS), 2006.
[32] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds. Journal of the
ACM (JACM), 63(2):17, 2016.
[33] F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Symp. on Principles of
Distributed Computing (PODC), 2006.
[34] N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193–201, 1992.
[35] N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441–454, 1993.
[36] L. Lovász. Combinatorial problems and exercises. North Holland, 1979.
[37] M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing,
15:1036–1053, 1986.
[38] M. Molloy and B. Reed. A bound on the total chromatic number. Combinatorica, 18(2):241–280, 1998.
[39] M. Molloy and B. Reed. Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer,
2001.
[40] M. Molloy and B. Reed. Asymptotically optimal frugal colouring. Journal of Combinatorial Theory, Ser. B,
100(2):226–246, 2010.
[41] M. Molloy and B. Reed. Colouring graphs when the number of colours is almost the maximum degree. Journal
of Combinatorial Theory, Series B, 109:134 – 195, 2014.
[42] M. Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete
Mathematics, 4(3):409–412, 1991.
[43] A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of Symposium on Theory of Computing(STOC), pages 581–592. ACM, 1992.
[44] A. Panconesi and A. Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding
bounds. SIAM Journal on Computing, 26(2):350–368, 1997.
[45] S. Pettie and H.-H. Su. Distributed coloring algorithms for triangle-free graphs. Information and Computation,
243:263–280, 2015.
[46] R. Ramaswami and K. K. Parhi. Distributed scheduling of broadcasts in a radio network. In Proc. of the Conference of the IEEE Computer and Communications Societies (INFOCOM). Technology: Emerging or Converging,
IEEE, pages 497–504 vol.2, 1989.
[47] B. Reed. ω, ∆, and χ. Journal of Graph Theory, 27(4):177–212, 1998.
[48] B. Reed. A strengthening of Brooks’ theorem. Journal of Combinatorial Theory, Series B, 76(2):136 – 149, 1999.
[49] J. Schneider, M. Elkin, and R. Wattenhofer. Symmetry breaking depending on the chromatic number or the
neighborhood growth. Journal of Theoretical Computer Science(TCS), 509:40–50, 2013.
[50] J. Schneider and R. Wattenhofer. A new technique for distributed symmetry breaking. In Symp. on Principles
of Distributed Computing(PODC), 2010.
[51] J. Schneider and R. Wattenhofer. An optimal maximal independent set algorithm for bounded-independence
graphs. Journal of Distributed Computing, 22(5):349–361, 2010.
[52] M. Szegedy and S. Vishwanathan. Locality based graph coloring. In Proc. of Symposium on Theory of Computing
(STOC), pages 201–207, 1993.

