An Optimal Distributed (∆ + 1)-Coloring Algorithm?

arXiv:1711.01361v1 [cs.DC] 3 Nov 2017

Yi-Jun Chang
University of Michigan

Wenzheng Li
IIIS, Tsinghua University

Seth Pettie∗
University of Michigan

Abstract
Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (∆ + 1)-list coloring in the randomized
LOCAL model running in O(log ∗ n + Detd (poly log n)) time, where Detd (n′ ) is the deterministic complexity of (deg +1)-list coloring (v’s palette has size deg(v) + 1) on n′ -vertex graphs.
This improves √upon a previous randomized algorithm of Harris, Schneider, and Su [18] with
complexity O( log ∆ + log log n + Detd (poly log n)), and is dramatically faster than the best
known
√ deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [14], with complexity
O( ∆ log2.5 ∆ + log∗ n).
Our algorithm appears to be optimal. It matches the Ω(log∗ n) randomized lower bound,
due to Naor [25] and sort of matches the Ω(Det(poly log n)) randomized lower bound due to
Chang, Kopelowitz, and Pettie [7], where Det is the deterministic complexity
of (∆ + 1)-list
√
′
coloring. The best known upper bounds on Detd (n′ ) and Det(n′ ) are both 2O( log n ) (Panconesi
and Srinivasan [26]) and it is quite plausible that the complexities of both problems are the
same, asymptotically.

∗

This work is supported by NSF grants CCF-1514383 and CCF-1637546.

1

Introduction

Much of what we know about the LOCAL model has emerged from studying the complexity of
four canonical symmetry breaking problems and their variants: maximal independent set (MIS),
(∆ + 1)-vertex coloring, maximal matching, and (2∆ − 1)-edge coloring. The palette sizes “∆ + 1”
and “2∆ − 1” are minimal to still admit a greedy sequential solution; here ∆ is the maximum degree.
Early work [23, 25, 2, 26, 24, 1] showed that all the problems are reducible to MIS, all four
problems require Ω(log∗ n) time, even with randomization;
all can be solved in O(poly(∆) + log∗ n)
√
time (optimal when ∆ is constant), or in 2O( log n) time for any ∆. Until recently, it was actually
consistent with known results that all four problems had the same complexity.
Kuhn, Moscibroda, and Wattenhofer(KWM) [21] proved
that the “independent set” problems
q

(MIS and maximal matching) require Ω min{ logloglog∆∆ , logloglogn n } time, with or without randomization, via a reduction from O(1)-approximate minimum vertex cover. This lower bound provably
separated MIS/maximal matching from simpler symmetry-breaking problems like O(∆2 )-coloring,
which can be solved in O(log∗ n) time [23].
We now know the KMW lower bounds cannot be extended to the canonical coloring problems,
nor to variants of MIS like (2, t)-ruling sets, for t ≥ 2 [6, 5, 15]. Elkin, Pettie, and Su [11] proved that
(2∆ − 1)-list edge coloring can be solved by a randomized
algorithm in O(log log n + Det(poly log n))

q
time, which shows that neither the Ω

log ∆
log log ∆

nor Ω

log n
log log n

KMW lower bound applied to

Det(n′ )

this problem. Here
represents the deterministic complexity of the problem in question on
n′ -vertex graphs. Improving on [5, 28], Harris, Schneider, and Su [18] proved a similar
separation for
√
(∆ + 1)-vertex coloring. Their randomized algorithm solves the problem in O( log ∆ + log log n +
Detd (poly log n)) time, where Detd is the complexity of (deg +1)-list coloring.
The “Det(poly log n)” terms in the running times of [11, 18] are a consequence of the graph
shattering technique applied to distributed symmetry breaking. Barenboim, Elkin, Pettie, and
Schneider [5] showed that all the classic symmetry breaking problems could be reduced in O(log ∆)
or O(log2 ∆) time, w.h.p., to a situation where we have independent subproblems of size poly log(n),
which can then be solved with the best available deterministic algorithm.1 Later, Chang, Kopelowitz,
and Pettie (CKP) [7] gave a simple proof illustrating why graph shattering is inherent to the LOCAL
model: the randomized
complexity of any locally checkable problem2 is at least its deterministic
√
complexity on log n-size instances.
The CKP lower bound explains why the state-of-the-art randomized symmetry breaking algorithms have such strange stated running times: they all depend on a randomized graph shattering
routine (Rand.) and a deterministic (Det.) algorithm.
•
•
•
•

√

O(log ∆ + 2O( log log n) ) for MIS
√
√
O( log ∆ + 2O( log log n) ) for (∆ + 1)-vertex coloring
O(log ∆ + (log log n)3 ) for maximal matching
O((log log n)8 ) for (2∆ − 1)-edge coloring

(Rand. due to [15]
(Rand. due to [18]
(Rand. due to [5]
(Rand. due to [11]

and
and
and
and

Det.
Det.
Det.
Det.

to
to
to
to

[26]),
[26]),
[12]),
[13]).

In each, the term that depends on n is the complexity of the best deterministic algorithm, scaled
down to poly log(n)-size instances. In general, improvements in the deterministic complexities of
these problems imply improvements to their randomized complexities, but only if the running times
1
In the case of MIS, the subproblems actually have size poly(∆) log n, but satisfy the additional property that
they contain distance-5 dominating sets of size O(log n), which is often just as good as having poly log(n) size. See [5,
§3] or [15, §4] for more discussion of this.
2
See Naor and Stockmeyer [25] or Chang and Pettie [8] for a formal definition of the class of locally checkable
labeling (LCL) problems.

1

are improved in terms of “n” rather than “∆.” For example, a recent line of research has improved
the complexity of (∆ + 1)-coloring √
in terms of ∆, from O(∆ + log∗ n) [4], to Õ(∆3/4 ) + log∗ n [3],
to the state-of-the-art bound of Õ( ∆) + log∗ n, due to Fraigniaud, Heinrich, and Kosowski [14].
These improvements do not have consequences for randomized coloring algorithms using graph
shattering [5, 18] since we can only assume ∆ = (log n)Ω(1) in the shattered instances.
A Technical History of Randomized (∆ + 1)-Coloring. In this paper we prove that√(∆ + 1)O( log log n) ,
list coloring can be solved in O(log∗ n + Detd (poly
√ log′ n)) time w.h.p., which is always 2
given the best known bound on Detd (n′ ) = 2O( log n ) [26]. Our algorithm seems to come close to
the Ω(log∗ n + Det(poly log n)) lower bound implied by [23, 25, 7], where Det is the deterministic
complexity of (∆ + 1)-list coloring. Intellectually, our algorithm builds on a succession of breakthroughs by Schneider and Wattenhofer [28], Barenboim, Elkin, Pettie, and Schneider [5], Elkin,
Pettie, and Su, [11], and Harris, Schneider, and Su [18], which we shall now review.
Schneider and Wattenhofer [28] gave the first evidence that the canonical coloring problems may
not be subject to the KMW lower bounds. They showed that when the palette size is (1 + ǫ)∆,
where ǫ = Ω(1) and ∆ > poly log n is sufficiently large, that vertex coloring could be solved in just
O(log∗ n) time, w.h.p. The key observation is that the number of excess colors (current palette
size minus number of uncolored neighbors) is non-decreasing over time. After O(log ǫ−1 ) rounds of
a standard coloring routine, the number of excess colors (ǫ∆) becomes larger than the uncolored
degree. At this point there is a dramatic transition, and the probability that a vertex remains
uncolored is reduced exponentially in each successive round: O(log∗ n) more rounds suffice. Of
course, in the (∆ + 1)-coloring problem there is just one excess color initially, so the problem
is how to create them. Elkin, Pettie, and Su [11] observed that if the graph is “(1 − ǫ)-locally
sparse,” that after one iteration of a random coloring routine, a significant number (Ω(ǫ∆)) of pairs
of vertices in the neighborhood N (v) get assigned the same color, thereby creating Ω(ǫ∆) excess
colors at v.3 The notion of local sparsity is especially useful for addressing the (2∆−1)-edge coloring
problem [11], since it can be phrased as (∆′ + 1)-vertex coloring the line graph (∆′ = 2∆ − 2), which
is (1/2 + o(1))-locally sparse.
Of course, in the vertex coloring problem we cannot count on any kind of local sparsity, so
the next challenge is to make local density also work to our advantage. Harris, Schneider, and
Su [18] developed a remarkable new graph decomposition that can be computed in O(1) rounds
of communication. The decomposition takes a parameter ǫ, and partitions the vertices into an
“ǫ-sparse” set, and several vertex-disjoint “ǫ-dense” components, each with weak diameter 2. The
sparse set can be colored in O(log ǫ−1 + log log n + Detd (poly log n)) time4 using [11] and [5]. Harris
et al. [18] proved that by coordinating the coloring decisions within each dense component, it takes
only O(log1/ǫ ∆ + log log n + Detd (poly log n)) time to color the dense sets, i.e., the bound improves
√
as ǫ → 0. The time for the overall algorithm is minimized by choosing ǫ = exp(−Θ( log ∆)).

1.1

New Results and Technical Overview

In this paper we give a fast randomized algorithm for (∆ + 1)-vertex coloring. It is based on a
hierarchical version of the Harris-Schneider-Su clustering with roughly log log ∆ levels determined
√
by an increasing sequence of sparsity thresholds (ǫ1 , . . . , ǫℓ ), with ǫi = ǫi−1 . Following [18], we
begin with a single iteration of a procedure OneShotColoring, in which a constant fraction of the
vertices are colored. The guarantee of this procedure is that any vertex v at the ith level (which
3

A graph is (1 − ǫ)-locally sparse if, for every v, the subgraph induced by N (v) has at most (1 − ǫ)
4
It is (1 − ǫ′ )-locally sparse according to Elkin et al.’s definition [11], for some ǫ′ depending on ǫ.

2

∆
2



edges.

Randomized
∗

O(log n + Detd (poly log n))
√
O( log ∆ + log log n + Detd (poly log n))

new
[18]
[5]

Deterministic
√
O( ∆ log2.5 ∆ + log∗ n)
O(∆3/4 log ∆

[4]

Upper

[28]

O(∆ log ∆ + log n)

Bounds

O(∆ log log n)

[22]

O(∆ log n)

[24, 1, 20]

Lower
Bounds

Ω(log∗ n)
√
Ω(Det( log n))

[25]
[7]

[3]

+ log n)

∗

O(log ∆ + Detd (poly log n))
√
O(log ∆ + log n)
O(log n)

[14]

∗

O(∆ + log n)
∗

O(∆2

[22]
[2]

∗

+ log n)

[16, 23]

O(∆O(∆) + log∗ n)
√
2O( log n)
√
2O( log n log log n)

[26]

Ω(log∗ n)

[23]

[17]
[2]

Table 1: Development of lower and upper bounds for distributed (∆ + 1)-list coloring in
the LOCAL model. The terms Det(n′ ) and Detd (n′ ) are the deterministic complexities
of (∆ + 1)-list coloring and (deg +1)-list coloring on n′ -vertex graphs. All algorithms
listed, except for [18] and ours, also solve the (deg +1)-list coloring problem.
is ǫi -dense but ǫi−1 -sparse), has Ω(ǫ2i−1 ∆) pairs of vertices in its neighborhood N (v) assigned the
same color, thereby creating that many excess colors in the palette of v.
At this point, the most natural way to proceed is to apply a Harris-Schneider-Su style coloring
procedure to each level, one by one, with the hope that each will take roughly constant time. The
reason is that O(log1/ǫi 1/poly(ǫi−1 )) = O(1), so in constant time we should be able to create a situation where any uncolored vertices have O(poly(ǫi−1 )∆) uncolored neighbors but Ω(ǫ2i−1 ∆) excess
colors in their palette. With such a large gap, a Schneider-Wattenhofer style coloring algorithm
should complete in O(1) additional steps. This approach does not seem to work. Moreover, doing
the layers one by one takes Ω(log log ∆) time.
In order to color ǫi -dense components efficiently we need to maintain relatively large lower bounds
on the available palette and relatively small upper bounds on the number of external neighbors
(outside the ǫi -dense component). Thus, it is important that when we first consider a vertex, we
have not already colored too many of its neighbors. Our algorithm partitions the vertices at level i
into large and small blocks, depending on how many vertices of their ǫi -dense components stay at
level i (because they are ǫi−1 -sparse). It also partitions the layers themselves into log∗ (∆) strata.
We show that by coloring the small blocks in each stratum, one stratum at a time, and then the
large blocks, that we can always guarantee a sufficiently large palette at each vertex when it is first
considered. Each of these coloring steps takes O(1) rounds of communication but may not color all
vertices. The vertices left uncolored are put in O(1) classes, some of which induce constant degree
graphs, which are colored in O(log∗ n) time, and some induce poly log n-size components, which are
colored in Detd (poly log n) time.

1.2

The LOCAL Model

The undirected input graph G = (V, E) and communications network are identical. Each v ∈
V hosts a processor that initially knows deg(v), a unique Θ(log n)-bit ID(v), and global graph
parameters n = |V | and ∆ = maxv∈V deg(v). In the (∆ + 1)-list coloring problem each vertex v also
3

has a set Ψ(v) of allowable colors, with |Ψ(v)| ≥ ∆ + 1. As vertices progressively commit to their
final color, we also use Ψ(v) to denote v’s available palette, excluding colors taken by its neighbors
in N (v). Each processor is allowed unbounded computation and has access to a stream of private
unbiased random bits. Time is partitioned into synchronized rounds of communication, in which
each processor sends one unbounded message to each neighbor. At the end of the algorithm, each v
declares its output label, which in our case is a color from Ψ(v) that is distinct from colors declared
by all neighbors in N (v). Refer to [23, 27] for more on the LOCAL model and variants.

1.3

Organization

In Section 2 we define a hierarchical decomposition based on [18] and a certain partition of the
vertices into log log ∆ layers and log∗ ∆ strata. Section 3 gives a high-level description of the
algorithm, which uses a variety of coloring routines whose guarantees are summarized in Lemmas 5–
10. Lemma 5 (cf. [5, 18]) shows that a procedure OneShotColoring creates many excess colors;
it is proved in Appendix B. Lemma 10 (cf. [28, 11]) analyzes a procedure ColorBidding, which
is a generalization of the Schneider-Wattenhofer coloring routing; it is proved in Appendix C.
Lemmas 6–9 analyze two versions of an algorithm DenseColoringStep, which is a generalization of
the Harris-Schneider-Su routine [18]; they are proved in Appendix D. Appendix A reviews some
standard concentration inequalities.

2

Hierarchical Decomposition

In this section, we extend the work of Harris, Schneider, and Su [18] to define a hierarchical decomposition of the vertices based on local sparsity. Let G = (V, E) be the input graph, ∆ be
the maximum degree, and ǫ ∈ (0, 1) be a parameter. An edge e = {u, v} is an ǫ-friend edge if
|N (u) ∩ N (v)| ≥ (1 − ǫ)∆. We call u an ǫ-friend of v if {u, v} is an ǫ-friend edge. A vertex v is
ǫ-dense if v has at least (1 − ǫ)∆ ǫ-friends, otherwise it is ǫ-sparse.
We write Vǫs (and Vǫd ) to be the set of ǫ-sparse (and ǫ-dense) vertices. Let v be a vertex in a
set S ⊆ V and V ′ ⊆ V . Define d¯S,V ′ (v) = |(N (v) ∩ V ′ ) \ S| to be the external degree of v with
respect to S and V ′ , and aS (v) = |S \ (N (v) ∪ {v})| to be the anti-degree of v with respect to S.
A connected component C of the subgraph induced by the ǫ-dense vertices and the ǫ-friend edges
is called an ǫ-almost clique. The following lemma summarizes some properties of ǫ-almost cliques
from [18].
Lemma 1 ([18]). Fix any ǫ < 1/5. The following conditions are met for each ǫ-almost clique C,
and each vertex v ∈ C. (i) d¯C,Vǫd (v) ≤ ǫ∆, (ii) aC (v) ≤ 3ǫ∆, (iii) |C| ≤ (1 + 3ǫ)∆, and (iv)
distG (u, v) ≤ 2 for each u, v ∈ C, i.e., C has weak diameter 2.

2.1

A Hierarchy of Almost Cliques

Throughout this section, we fix some increasing sequence of sparsity parameters (ǫ1 , . . . , ǫℓ ) and
a subset of vertices V ⋆ ⊆ V , whose meaning will be explained shortly. The sequence (ǫ1 , . . . , ǫℓ )
always adheres to Definition 1.
Definition 1. A sequence (ǫ1 , . . . , ǫℓ ) is a valid sparsity sequence if the following conditions are
−(i−1)
√
, and (ii) ǫ1ℓ ≥ K for some large enough constant K.
met: (i) ǫi = ǫi−1 = ǫ21

4

Layers. Define V1 = V ⋆ ∩ Vǫd1 , and Vi = V ⋆ ∩ (Vǫdi \ Vǫdi−1 ), for i > 1. Define Vsp = V ⋆ ∩ Vǫsℓ =
V ⋆ \ (V1 ∪ · · · ∪ Vℓ ). It is clear that (V1 , . . . , Vℓ , Vsp ) is a partition of V ⋆ . We call Vi the layer-i
vertices, and call Vsp the sparse vertices. In other words, Vi is the subset of V ⋆ that are ǫi -dense but
ǫi−1 -sparse. Remember that the definition of sparsity is with respect to the entire graph G = (V, E)
not the subgraph induced by V ⋆ .
Strata. Define ξ1 = ǫ1 , and ξk S= 1/ log(1/ξk−1 ) for k > 1. By definition, the 1st stratum is
W1 = V1 . The kth stratum Wk = i : ǫi ∈(ξk−1 ,ξk ] Vi spans those layers whose sparsity parameter lies
in (ξk−1 , ξk ]. Define s ≤ log∗ (1/ǫ1 ) to be the index of the last stratum Ws .
Blocks. The layer-i vertices Vi are partitioned into blocks as follows. Let {C1 , C2 , . . .} be the set
of ǫi -almost cliques, and let Bj = Cj ∩ Vi . Then (B1 , B2 , . . .) is a partition of Vi , and we call each
Bj a layer-i block. If layer i is in stratum k, then Bj is also called a stratum-k block.
A layer-i block B is a descendant of a layer-i′ block B ′ , i < i′ , if B and B ′ are both subsets of
the same ǫi′ -almost clique. Therefore, the set of all blocks in all layers naturally forms a rooted tree
T . (The root represents Vsp ; every other node represents a block in some layer.)
∆
and there is
log2 (1/ξk )
∆
′
and |B | ≥ log2 (1/ξ
.
k′ )

Definition 2. A stratum-k block B is a large block if |B| ≥

k′

B′

(k′

block
small block.

≥ k) such that

B′

is ancestral to B in T

no other stratumOtherwise B is a

∆
in the above definition depends on the stratum in which the
Notice that the threshold log2 (1/ξ
k)
block B resides. By definition, for any two blocks B and B ′ in different layers, if B is a descendant
of B ′ , then B and B ′ cannot both be large.
Define ViS , ViL , WkS , and WkL to be, respectively, the sets of all vertices in layer-i small blocks,
layer-i large blocks, stratum-k small blocks, and stratum-k large blocks. Notice that (ViS , ViL ) is a
partition of Vi and (WkS , WkL ) is a partition of Wk .

Super-blocks. Suppose stratum k spans layers i′ , i′ + 1, . . . , i. Let {C1 , C2 , . . .} be the set of
ǫi -almost cliques, and let Rj = Cj ∩ Wk . Then (R1 , R2 , . . .) is a partition of Wk , and we call each
Rj a stratum-k super-block.
Overview of Our Algorithms. The decomposition and T are trivially computed in O(1) rounds
of communication. Let us briefly explain how our algorithm uses this hierarchical decomposition.
The first step is to execute an O(1)-round coloring procedure (OneShotColoring) which colors a small
constant fraction of the vertices in G. Let V ⋆ be the remaining uncolored vertices. The set V ⋆ is
partitioned into subsets (W1S , . . . , WsS , W1L , . . . , WsL , Vsp ) based on the hierarchical decomposition
with respect to a particular sparsity sequence (ǫ1 , . . . , ǫℓ ). We color the vertices of V ⋆ \ Vsp in
s + 2 = O(log∗ (1/ǫ1 )) stages according to the ordering (WsS , . . . , W1S , W ′ , W1L ), where W ′ is defined
as W2L ∪ · · · ∪ WsL . At the end of this process a small portion of vertices U ⊆ V ⋆ \ Vsp may remain
uncolored. However, they all have sufficiently large palettes such that U ∪ Vsp can be colored
efficiently in O(log∗ n) time.
The purpose of processing the small blocks before the large blocks is to ensure that the vertices
in small blocks still have an adequate number of colors in their palettes when they are considered. Lemma 2 specifies exactly what an adequate number of colors is. That is, regardless of how
S , . . . , W S ) are colored, each v ∈ W S still has at least ∆/2 log 2 (1/ξ ) excess colors in its
(WsS , Ws−1
k
k+1
k
palette, beyond those needed to color WkS .
5

Lemma 2. Suppose that |N (v) ∩ V ⋆ | ≥ ∆/3. For each k ∈ [1, s] and each v ∈ WkS , we have
S
∪ W1L ∪ · · · ∪ WsL ∪ Vsp )| ≥ ∆/2 log2 (1/ξk ).
|N (v) ∩ (W1S ∪ · · · ∪ Wk−1
Before proving Lemma 2 we first establishing a useful property of the block hierarchy T .

Lemma 3. Let C
an ǫi -almost clique and C1 , . . . , Cl be the ǫi−1 -almost cliques contained in C.
Pbe
l
Either l = 1 or j=1 |Cj | ≤ 2(3ǫi + ǫi−1 )∆. In particular, if B is the layer-i block contained in
C, either B has one child in T or the number of vertices in all strict descendants of B is at most
2(3ǫi + ǫi−1 )∆ < 7ǫi ∆.
P
Proof. Suppose, for the purpose of obtaining a contradiction, that l ≥ 2 and lj=1 |Cj | > 2(3ǫi +
P
ǫi−1 )∆. W.l.o.g. suppose C1 is smallest, so lj=2 |Cj | > (3ǫi + ǫi−1 )∆. Any v ∈ C1 is ǫi−1 -dense
and therefore has at least (1 − ǫi−1 )∆ neighbors that are ǫi−1 -friends. By definition any ǫi−1 -friend
is also an ǫi friend, so this set is contained in C. By Lemma 1, |C| ≤ (1 + 3ǫi )∆. Thus, by the
pigeonhole principle, some ǫi−1 -friend of v must be in C2 ∪ · · · ∪ Cl , contradicting the fact that C1
is a connected component in the subgraph induced by ǫi−1 -dense vertices and ǫi−1 -friend edges.
Proof of Lemma 2. Recall that v ∈ WkS lies in stratum k and that by assumption, |N (v)∩V ⋆ | ≥ ∆/3.
Suppose stratum k spans layers [i0 , i1 ] and let v ∈ B where B is a layer-i small block, i ∈ [i0 , i1 ].
We put the neighbors of v into one of several groups.
1. Neighbors in W1 ∪ · · · ∪ Wk−1 ∪ Vsp .
2. The remaining neighbors in blocks that are neither in ancestors nor descendants of B in T .
3. Neighbors in all ancestors of B and those stratum-k descendants of B.
Define A1 = |N (v) ∩ (W1 ∪ · · · ∪ Wk−1 ∪ Vsp )|. If A1 ≥ ∆/2 log 2 (1/ξk ) then the conclusion of
the lemma already holds, so assume otherwise. Let A2 be the number
P of neighbors in blocks that
are neither in ancestors nor descendants of v. By Lemma 1, A2 ≤ ℓj=1 ǫj ∆ ≤ 2ǫℓ ∆.
We now turn to A3 . Let Ci1 be the ǫi1 -almost clique containing B. It follows from Lemma 3
that there is some index i⋆ ∈ [i0 , i1 ] such that
(i) Ci1 ⊇ Ci1 −1 ⊇ · · · ⊇ Ci⋆ .

(ii) Each Cj , j ∈ [i⋆ , i1 − 1], is an ǫj -almost clique and is the only such almost clique contained in
Cj+1 .
(iii) Either i⋆ = i0 or Ci⋆ contains at least two ǫi⋆ −1 -almost cliques.

If i⋆ 6= i0 then, by Lemma 3 again, the number of vertices in Ci⋆ that are in ǫi⋆ −1 -almost cliques is
at most 7ǫi⋆ ∆. Define Bi⋆ to be the block contained in Ci⋆ and let B be the set of all blocks that
are ancestors of Bi⋆ in T .
We first entertain the possibility that all blocks in B are small. Note that since B spans many
strata, the definition of small is different for each stratum. It follows from Definition 1 that there
are fewer than log log(1/ξk′ −1 ) layers in stratum k′ . Thus, the maximum number of neighbors that
v has in B is
s
X
∆
· log log(1/ξk′ −1 )
(By definition of small)
2
′)
log
(1/ξ
k
′
k =k
=

s
X

k ′ =k

∆
log(1/ξk′ )

(log log(1/ξk′ −1 ) = log(1/ξk′ ))

≤ 2∆/ log(1/ξs ) ≤ 2∆/ log log(1/ǫℓ )

(ξs−1 < ǫℓ ≤ ξs )
6

In this case, the the number of neighbors contributed by group 3 is at most A3 = 7ǫi⋆ ∆ +
2∆/ log log(1/ǫℓ ). Thus, the number of v’s neighbors in V ⋆ is at most
A1 + A2 + A3 ≤ ∆/ log2 (1/ξk ) + 2ǫℓ ∆ + 7ǫi⋆ ∆ + 2∆/ log log(1/ǫℓ ) ≪ ∆/3,
contradicting the assumption of the lemma. (Recall that ǫℓ < 1/K for some sufficiently large
constant K.) Thus, there must exist some stratum-k′ block B ′ ∈ B containing at least ∆/ log2 (1/ξk′ )
neighbors of v. According to Definition 2, this implies that either B ′ or a strict ancestor of B ′ is
large. Let B ′′ be the (unique) large ancestor of B ′ , and suppose it is in layer i′′ and stratum k′′ .
According to Lemma 1, the number of neighbors of v in B ′′ is at least
|B ′′ | − 3ǫi′′ ∆ ≥

∆
∆
∆
∆
− 3ǫi′′ ∆ ≥
− 3ξk′′ ∆ ≥
≥
.
2
2
2
log (1/ξk′′ )
log (1/ξk′′ )
2 log (1/ξk′′ )
2 log (1/ξk )
2

Thus N (v) ∩ WkL′′ ≥ ∆/2 log 2 (1/ξk ).

3

Main Algorithm

Our algorithm follows the graph shattering framework [5]. In each step of the algorithm, we specify
an invariant that all vertices must satisfy in order to continue to participate. Those bad vertices
that violate the invariant are removed from consideration; they form connected components of size
poly log n w.h.p., so we can color them later in Detd (poly log n) time. More precisely, the emergence
of the small components is due to the following lemma [5, 12].
Lemma 4 (The Shattering Lemma). Consider a randomized procedure that generates a subset of
vertices B ⊆ V . Suppose that for each v ∈ V , we have Pr[v ∈ B] ≤ ∆−(2c+1) , and this holds even if
′
the random bits not in N c (v) are determined adversarially. Then, with probability at least 1 − n−c ,
each connected component in the graph induced by B has size at most O(c′ ∆2c log n).
Since our algorithm consists of t = O(log∗ ∆) steps, whether a vertex v is bad actually depends
on random bits in its distance-t neighborhood. Nonetheless, we are still able to apply Lemma 4.
The reason is that we are able to show that each vertex v becomes bad in one particular step with
probability at most ∆−x (for any specified constant x), and this is true regardless of the outcomes
in all previous steps and the choices of random bits outside of a constant-radius of v.
√
The sparsity sequence for our algorithm is defined by ǫ1 = ∆−1/10 , ǫi = ǫi−1 for i > 1, and ℓ
is the largest index such that ǫ1ℓ ≥ K for some sufficiently large K.

3.1

Initial Coloring Step

At any point in time, the number of excess colors at v is the size of v’s remaining palette minus
the number of v’s uncolored neighbors. This quantity is obviously non-decreasing over time. We
first show that in O(1) time, we can color a portion of the vertices such that each remaining
uncolored vertex has a certain number of excess colors, which depends on its local sparsity. Refer
to Appendix B for proof.
Lemma 5. There is an O(1)-round algorithm that colors a subset of vertices such that each ǫ-sparse
vertex v with deg(v) ≥ 0.9∆ satisfies the following conditions.
• With probability 1 − exp(−Ω(∆)), the number of uncolored neighbors of v is at least ∆/2.
• With probability 1 − exp(−Ω(ǫ2 ∆)), v has at least Ω(ǫ2 ∆) excess colors.
7

We execute the algorithm of Lemma 5. In order to proceed a vertex must satisfy both of the
following conditions: (i) if v is ǫℓ -dense, the number of uncolored neighbors of v is at least ∆/2; (ii)
if v is ǫi -dense but ǫi−1 -sparse, v must have Ω(ǫ2i−1 ∆) excess colors. If either fails to hold, v is put
in the set Vbad .
Define V ⋆ to be the set of uncolored vertices that are not in Vbad . We compute the partition
⋆
V = W1S ∪· · ·∪WsS ∪W1L ∪· · ·∪WsL ∪Vsp . Notice that we invoke the conditions of Lemma 5 only with
ǫ ≥ ǫ1 = ∆−1/10 . Thus, if ∆ = Ω(log2 n), then with high probability (i.e., 1 − 1/poly(n)), Vbad = ∅.
Otherwise, each component of Vbad must, by Lemma 4, have size O(poly(∆) · log n) = O(poly log n),
w.h.p. We do not invoke a deterministic algorithm to color Vbad just yet. In subsequent steps of the
algorithm, we continue to add “bad vertices” to Vbad . These vertices are colored at the end of the
algorithm.

3.2

Coloring Vertices by Stratum

In this section, we show how we can color most of the vertices in W1 , . . . , Ws , leaving a small portion
of uncolored vertices U , each having a large number of excess colors. We do the coloring in s + 2
stages in this order (i) s − 1 stages of small blocks: WsS , . . . , W2S , (ii) first layer small blocks W1S ,
(iii) large blocks W ′ = W2L ∪ · · · ∪ Wh , and (iv) first layer large blocks W1L .
Notice that due to Lemma 2, at the time we begin to process WkS , each vertex v ∈ WkS must
have at least ∆/2 log2 (1/ξk ) excess colors w.r.t. WkS . That is, its palette size minus the number
of its neighbors in WkS is large. If the condition |N (v) ∩ V ⋆ | ≥ ∆/3 in Lemma 2 is not met, then
it means that at least (∆/2 − ∆/3) neighbors of v were included in Vbad after the initial coloring
step, and so v automatically has at least ∆/6 > ∆/2 log2 (1/ξk ) excess colors w.r.t. WkS . Refer to
Appendix D for proofs of Lemmas 6–9.
Lemma 6 (Small blocks; strata other than 1). Suppose that each vertex v ∈ WkS has at least
∆/2 log2 (1/ξk ) excess colors w.r.t. WkS . There is an O(1)-time algorithm that colors a subset of WkS
meeting the following condition. For each v ∈ V ⋆ and each layer i in stratum k, with probability at
least 1 − exp(−Ω(poly(∆))), the number of uncolored layer-i neighbors of v in ViS is at most ǫ5i ∆.
Vertices that violate this property join the set Vbad .
Lemma 7 (Small blocks; stratum 1). Suppose that each vertex v ∈ W1S has at least ∆/2 log 2 (1/ξ1 )
excess colors w.r.t. W1S . There is an O(1)-time algorithm that colors a subset of W1S meeting the
following conditions, for any specified constant c. If ∆ = O(log4 n), then each v ∈ W1S is colored
with probability at least 1 − ∆−c , and all uncolored vertices in W1S joins Vbad . If ∆ = Ω(log4 n),
then, with probability at at least 1 − n−c , the remaining uncolored vertices of W1S are partitioned
into 2 sets X and R such that (i) the subgraph induced by R has maximum degree O(1), (ii) each
connected component in the graph induced by X has size at most poly log n.
Lemma 8 (Large blocks; strata other than 1). There is an O(1)-time algorithm that colors a subset
of W ′ meeting the following condition. For each v ∈ V ⋆ and each layer i ∈ [2, ℓ], with probability at
least 1 − exp(−Ω(poly(∆))), the number of uncolored layer-i neighbors of v in ViL is at most ǫ5i ∆.
Vertices that violate this property join the set Vbad .
Lemma 9 (Large blocks; stratum 1). Let α be a sufficiently large constant, and let c be any constant.
There is an O(1)-time algorithm that colors a subset of W1L and puts the remaining uncolored vertices
in one of X1 , X2 , R or Vbad . It is required that the subgraph induced by R has constant degree, and
every component in the subgraph induced by X1 and the subgraph induced by X2 has size at most
poly log n. If ∆ ≤ logα n, then X1 = X2 = ∅, and each v ∈ W1L is added to Vbad with probability at
most ∆−c . If ∆ ≥ logα n, with probability 1 − 1/n−c , no vertex in W1L is added to Vbad .
8

We apply Lemmas 6–9 to color the vertices in V ⋆ \ Vsp . The subgraph induced by R (Lemma 7
and Lemma 9) has constant degree. We immediately color these vertices using any O(log∗ n)-time
algorithm. All vertices in X (Lemma 7), X1 , or X2 (Lemma 9) are colored in time Detd (poly log n)
using a deterministic algorithm. The vertices in X, X1 , X2 do not join Vbad .
Any vertex in V ⋆ that violates at least one condition specified in the lemmas is added to the set
Vbad . All remaining uncolored vertices join the set U .

3.3

Coloring the Remaining Vertices

At this point all uncolored vertices are in U ∪ Vsp ∪ Vbad . We show that U ∪ Vsp can be colored
efficiently in O(log∗ ∆) time.
We first consider the set U . Let G′ be the directed acyclic graph induced by U , where all edges
are oriented from the sparser to the denser endpoint. In particular, an edge e = {u, u′ } is oriented
as (u, u′ ) if u is at layer i, u′ at layer i′ , and i > i′ , or if u and u′ are at the same layer i and
ID(u) > ID(u′ ). We write Nout (v) to denote the set of out-neighbors of v.
For each layer-i vertex v in G′ , and each layer-j, the number of layer-j neighbors P
of v in G′ is
5
at most O(ǫj ∆), due to Lemmas 6 and 8. The out-degree of v is therefore at most ij=1 ǫ5j ∆ =
2
O(ǫ5i ∆) = O(ǫ2.5
i−1 ∆). The number of excess colors at v is at least Ω(ǫi−1 ∆). Thus, there is an
√
Ω(1/ ǫi−1 )-factor gap between the palette size of v and the out-degree of v.
We write Ψ(v) to denote the set of available colors of v. There exists a constant η > 0 such
def

that, for each i ∈ [2, ℓ] and each layer-i vertex v in G′ , we have |Ψ(v)| − outdeg(v) ≥ ηǫ2i−1 ∆ = pv .
There is a constant C > 0 such that for each i ∈ [2, ℓ] and each layer-i vertex v ∈ U satisfies
!
i
i
X
X
X
ǫ2.5
j−1 ∆
O(ǫ0.5
=
O 2
1/pu ≤
j−1 ) < 1/C.
ǫ
∆
j−1
j=1
j=1
u∈Nout (v)

Lemma 10 is applied to color nearly all vertices in U in O(log∗ ∆) time, with any remaining
uncolored vertices added to Vbad . Notice that in our setting, the parameters of Lemma 10 are
√
p⋆ ≥ ηǫ21 ∆ = Ω(∆8/10 ) and d⋆ ≤ ∆. Thus, the probability that a vertex is bad is exp(−Ω( p⋆ )) +
d⋆ exp(−Ω(p⋆ )) = exp(−Ω(∆2/5 )) (by Lemma 10). Refer to Appendix C for proof of Lemma 10.
Lemma 10. Consider a directed acyclic graph, where vertex v is associated with a parameter pv ≤
|Ψ(v)| − outdeg(v).
We write p⋆ = minv∈V pv . There is a constant C > 0 such that all vertices
P
v satisfy u∈Nout (v) 1/pu ≤ 1/C. Let d⋆ be the maximum out-degree of the graph. There is an
O(log∗ (p⋆ ))-time algorithm achieving the following. Each vertex v remains uncolored with probability
√
at most exp(−Ω( p⋆ )) + d⋆ exp(−Ω(p⋆ )). This is true even if the random bits generated outside a
constant radius around v are determined adversarially.
The set Vsp can be colored in a similar way using the above lemma. We let G′′ be any
acyclic orientation of the graph induced by Vsp (e.g., orienting each edge {u, v} to the vertex
v such that ID(v) > ID(u)). The number of available colors of each v ∈ Vsp minus its outdegree is at least Ω(ǫ2ℓ ∆), which is at least γ∆, for some constant γ > 0 (according to the
way
P we select the sparsity sequence). We define pv = γ∆ < |Ψ(v)| − outdeg(v). We have
u∈Nout (v) (1/pu ) ≤ outdeg(v)/(γ∆) ≤ 1/γ. Thus, we can apply Lemma 10 with C =√γ. Notice that both p⋆ and d⋆ are Θ(∆), and so the probability that a vertex is bad is exp(−Ω( ∆)).
We add all remaining uncolored vertices in Vsp ∪ U to Vbad . We are now ready to color Vbad . If
∆ ≥ logα n, then Vbad = ∅, w.h.p., in view of the probabilities stated in Lemmas 6–10. Otherwise,
∆ ≤ logα n, and by Lemma 4, each connected component of Vbad has size at most poly(∆) ·
poly log n = poly log n. Thus, it takes Detd (poly log n) to color all bad vertices Vbad .
9

3.4

Time Complexity

The time for the initial coloring step is O(1). The time for processing each of WsS , . . . , W2S , W1S ,
W ′ , W1L is also O(1), or O(s) = O(log∗ ∆) in total. The time to color the vertices of U ∪ Vsp not
marked bad is O(log∗ ∆). In addition, we invoke O(1) times
(i) an O(log∗ n)-time algorithm for coloring a bounded degree graph (i.e., the set R in Lemma 7
and Lemma 9), and
(ii) a Detd (poly log n)-time algorithm for coloring components of size poly log(n) (i.e., the sets X,
X1 , and X2 in Lemma 7 and Lemma 9, and the bad vertices Vbad ).
Thus, the total time complexity is O(log∗ n + Detd (poly log n)).
Theorem 1. There is an algorithm that computes a (∆ + 1)-list coloring, with high probability, in
O(log∗ n + Detd (poly log n)) time.
There is a universal constant c such that the size of each connected component of Vbad , X,
X1 , and X2 is at most logc n, w.h.p. If each vertex is allowed to have logc n extra colors, then
we can invoke the O(log∗ ∆)-time algorithm of Lemma 10 to color them (rather than spending
Detd (poly log n) time), thereby improving the time complexity greatly. Notice that if every vertex
is ǫ-sparse, with ǫ2 ∆ sufficiently large, then the algorithm of Lemma 5 gives every vertex Ω(ǫ2 ∆)
excess colors, w.h.p. Thus, we have the following theorems.
Theorem 2. There is a universal constant c such that there is a randomized algorithm that, w.h.p.,
computes a (∆ + logc n)-list coloring in O(log∗ n) time.
Theorem 3. There is a universal constant c such that the following holds. Suppose each vertex is
ǫ-sparse, and ǫ2 ∆ = logc n. There is a randomized algorithm that, w.h.p., computes a (∆ + 1)-list
coloring in O(log∗ n) time.
Remark 1. Notice that Theorem 3 insists on every vertex being ǫ-sparse, as defined in Section 2.
It is straightforward to show connections between this definition of sparsity and others standard
measures from the literature. For example, such a graph is (1 − ǫ′ )-locally sparse (according to the
definition of [11]), where ǫ′ = Ω(ǫ2 ). Similarly, any (1 − ǫ′ )-locally sparse graph is Ω(ǫ′ )-sparse.
Graphs of degeneracy d ≤ (1 − ǫ′ )∆ or arboricity λ ≤ (1/2 − ǫ′ )∆ are trivially (1 − Ω(ǫ′ ))-locally
sparse [5].

4

Conclusion

∗
We have presented a new randomized (∆ + 1)-list coloring algorithm that requires
√ O(log n +
∗
Detd (poly log n)) rounds of communication, which comes close to the Ω(log n + Det( log
√n)) lower5
∗
bound implied by Naor [25] (Ω(log n)) and Chang, Kopelowitz, and Pettie [7] (Ω(Det( log n))).
When ∆ is unbounded (relative to n), the best known algorithms for√(∆ + 1)- and (deg +1)-list
coloring are the same: they use Panconesi and Srinivasan’s [26] 2O( log n) -time construction of
network decompositions. Even if optimal (O(log n), O(log n))-network decompositions could be
computed for free, we still do not know how to solve (∆ + 1)-list coloring faster than O(log2 n) time.
Thus, reducing the Detd (poly log n) term in our running time below O((log log n)2 ) will require a
radically new approach to the problem.
It is an open problem to generalize our algorithm (or that of [18]) to solve the (deg +1)-coloring
problem. The main difficulty is to extend the definition of “ǫ-friend” to account for neighbors of
different degrees, while still preserving the useful properties of ǫ-dense clusters from Lemma 1.
5

Recall that Det and Detd are the deterministic complexities of (∆ + 1)-list coloring and (deg +1)-list coloring.

10

References
[1] N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal
independent set problem. J. Algor., 7:567–583, 1986.
[2] B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality
in distributed computation. In Proceedings 30th IEEE Symposium on Foundations of Computer
Science (FOCS), pages 364–369, 1989.
[3] L. Barenboim. Deterministic (∆ + 1)-coloring in sublinear (in ∆) time in static, dynamic
and faulty networks. In Proceedings of the 2015 ACM Symposium on Principles of Distributed
Computing (PODC), pages 345–354, 2015.
[4] L. Barenboim, M. Elkin, and F. Kuhn. Distributed (∆ + 1)-coloring in linear (in ∆) time.
SIAM J. Comput., 43(1):72–95, 2014.
[5] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry
breaking. J. ACM, 63(3):20:1–20:45, 2016.
[6] T. Bisht, K. Kothapalli, and S. V. Pemmaraju. Brief announcement: Super-fast t-ruling sets.
In Proceedings 33rd ACM Symposium on Principles of Distributed Computing (PODC), pages
379–381, 2014.
[7] Y.-J. Chang, T. Kopelowitz, and S. Pettie. An exponential separation between randomized
and deterministic complexity in the LOCAL model. In Proceedings 57th IEEE Symposium on
Foundations of Computer Science (FOCS), pages 615–624, 2016.
[8] Y.-J. Chang and S. Pettie. A time hierarchy theorem for the LOCAL model. In Proceedings
58th IEEE Symposium on Foundations of Computer Science (FOCS), 2017.
[9] D. P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized
Algorithms. Cambridge University Press, 2009.
[10] D. P. Dubhashi and D. Ranjan. Balls and bins: A study in negative dependence. J. Random
Structures and Algs., 13(2):99–124, 1998.
[11] M. Elkin, S. Pettie, and H.-H. Su. (2∆−1)-edge coloring is much easier than maximal matching
in the distributed setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 355–370, 2015.
[12] M. Fischer and M. Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma
with implications on complexity hierarchies. In Proceedings 31st International Symposium on
Distributed Computing (DISC), pages 18:1–18:16, 2017.
[13] M. Fischer, M. Ghaffari, and F. Kuhn. Deterministic distributed edge coloring via hypergraph
maximal matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science
(FOCS), 2017.
[14] P. Fraigniaud, M. Heinrich, and A. Kosowski. Local conflict coloring. In Proceedings 57th
Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 625–634, 2016.
[15] M. Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings
27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270–277, 2016.
11

[16] A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. In
Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 315–324.
ACM, 1987.
[17] A. V Goldberg and S. A Plotkin. Parallel (δ+ 1)-coloring of constant-degree graphs. Information Processing Letters, 25(4):241–245, 1987.
[18] D. Harris, J. Schneider, and H.-H. Su. Distributed (∆ + 1)-coloring in sublogarithmic rounds.
In Proceedings 48th ACM Symposium on Theory of Computing (STOC), pages 465–478, 2016.
[19] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the
American Statistical Association, 58(301):13–30, 1963.
[20] Ö. Johansson. Simple distributed ∆ + 1-coloring of graphs. Info. Proc. Lett., 70(5):229–232,
1999.
[21] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds.
J. ACM, 63(2):17:1–17:44, 2016.
[22] F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proceedings
25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 7–15,
2006.
[23] N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992.
[24] M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036–1053, 1986.
[25] M. Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM
J. Discrete Mathematics, 4(3):409–412, 1991.
[26] A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition.
J. Algor., 20(2):356–374, 1996.
[27] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
[28] J. Schneider and R. Wattenhofer. A new technique for distributed symmetry breaking. In
Proceedings 29th Annual ACM Symposium on Principles of Distributed Computing (PODC),
pages 257–266, 2010.

12

A

Concentration Bounds

We make use of the following standard tail bounds [9]. Let X be binomially distributed with
parameters (n, p), i.e., it is the sum of n independent 0-1 variables with mean p. We have the
following bound on the lower tail of X:


−(µ − t)2
, where t < µ = np.
Pr[X ≤ t] ≤ exp
2µ
Chernoff bounds also hold when X is the sum of n negatively correlated 0-1 random variables [10, 9]
with mean p, i.e., total independent is not required. We use a bound on the upper tail of X with
mean µ = np.
(
2
exp( −δ3 µ ) if δ ∈ [0, 1]
Pr[X ≥ (1 + δ)µ] ≤
exp( −δµ
if δ > 1.
3 )
Pn
Consider the scenario where X =
i=1 Xi , and each Xi is an independent random variable
bounded by the interval [ai , bi ]. Let µ = E[X]. Then we have the following concentration bound
(Hoeffding’s inequality) [19].


−2(δµ)2
P
.
Pr[X ≥ (1 + δ)µ] ≤ exp
n
2
i=1 (bi − ai )

B

Analysis of OneShotColoring — Proof of Lemma 5

Fix a constant parameter p ∈ (0, 1/4). The procedure OneShotColoring is a simple O(1)-round
coloring procedure that breaks ties by ID. Define N ∗ (v) = {u ∈ N (v) | ID(u) < ID(v)} to be the
neighbors of v with higher priority than v.
OneShotColoring. Each uncolored vertex v decides to participate independently with probability
p. Each participating vertex v selects a color c(v) from its palette Ψ(v) uniformly at random.
A participating vertex v successfully colors itself if c(v) is not chosen by any vertex in N ∗ (v).
After OneShotColoring, each vertex v removes all colors from Ψ(v) that are taken by some
neighbor u ∈ N (v). The number of excess colors at v is the size of v’s remaining palette minus
the number of uncolored neighbors of v. We prove one part of Lemma 5 by showing that after a
call to OneShotColoring, the number of excess colors at any ǫ-sparse v is Ω(ǫ2 ∆), with probability
1 − exp(−Ω(ǫ2 ∆)). Similar but weaker lemmas were proved in [11, 18]. The corresponding lemma
from [11] does not apply to list coloring, and the corresponding lemma from [18] obtains a high
probability bound only if ǫ4 ∆ = Ω(log n). Optimizing this requirement is of importance, since this
is the threshold regarding how locally sparse a vertex needs to be in order to obtain excess colors
from OneShotColoring. The remainder of this section constitutes a proof of Lemma 5.
Consider an execution of OneShotColoring with any constant p ∈ (0, 1/4). Recall that we assume
1/ǫ ≥ K, for some large enough constant K. Let v be an ǫ-sparse vertex. Define the following two
numbers.
f1 (v) : the number of vertices u ∈ N (v) that successfully color themselves by some c ∈
/ Ψ(v).
f2 (v) : the number of colors c ∈ Ψ(v) such that at least two vertices in N (v) successfully color
themselves c.
13

It is clear that f1 (v)+ f2 (v) is a lower bound on the number of excess colors at v after OneShotColoring. Our first goal is to show that f1 (v)+f2 (v) = Ω(ǫ2 ∆) with probability at least 1−exp(−Ω(ǫ2 ∆)).
We divide the analysis into two cases (Lemma 13 and Lemma 14), depending on whether f1 (v) or
f2 (v) is likely to be the dominant term. For any v, the preconditions of either Lemma 13 or
Lemma 14 are satisfied. Our second goal is to show that for each vertex v of degree at least 0.9∆,
with high probability, at least (1 − 1.1p)|N (v)| > ∆/2 neighbors of v remain uncolored after after
OneShotColoring. This is done in Lemma 15.
Lemmas 11 and 12 establish some generally useful facts of OneShotColoring, which are used in
the proofs of Lemma 13 and 14.
Lemma 11. Let Q be any set of colors, and let S be any set of vertices with size at most 2∆. The
number of colors in Q that are selected by some vertices in S is less than |Q|/2 with probability at
least 1 − exp(−Ω(|Q|)).
Proof. Let Ec denote the event that color c is selected by at least one vertex in S. Then Pr[Ec ] ≤
p|S|
∆+1 < 2p < 1/2, since p < 1/4 and |S| ≤ 2∆. Moreover, the collection of events {Ec } are negatively
correlated [10].
Let X denote the number of colors in Q that are selected by some vertices in S. By linearity of
,
expectation, µ = E[X] < 2p · |Q|. Thus, by a Chernoff bound, with δ = (1/2)−2p
2p
Pr[X ≥ (1 + δ)µ = |Q|/2] ≤ exp(−δ2 µ/3) = exp(−Ω(|Q|)),
as desired.
Lemma 12. Fix a sufficiently small ǫ > 0. Consider a set of vertices S = {u1 , . . . , uk } with
cardinality ǫ∆/2. Let Q be a set of colors such that each ui ∈ S satisfies |Ψ(ui )∩Q| ≥ (1−ǫ/2)(∆+1).
Moreover, each ui ∈ S is associated with a vertex set Ri such that (i) S ∩ Ri = ∅, and (ii) |Ri | ≤ 2∆.
Then, with probability at least 1 − exp(−Ω(ǫ2 ∆)), there are at least pǫ∆/8 vertices ui ∈ S such that
the color c selected by ui satisfies (i) c ∈ Q, and (ii) c is not selected by any vertex in Ri ∪ S \ {ui }.
Proof. Assume that S = (u1 , . . . , uk ) is sorted in increasing order by ID. Define Qi = Ψ(ui ) ∩ Q.
We call a vertex ui happy if ui selects some color c ∈ Q and c is not selected by any vertex in
Ri ∪ S \ {ui }. Define the following events.
Eigood : ui selects a color c ∈ Qi such that c is not selected by any vertices in Ri .
Eibad : the number of colors in Qi that are selected by some vertices in Ri is at least |Qi |/2.
Eirepeat : the color selected by ui is also selected by some vertices in {u1 , . . . , ui−1 }.
P
Let Xi be the indicator random variable that either Eigood or Eibad occurs, and let X = ki=1 Xi .
P
Let Yi be the indicator random variable that Eirepeat occurs, and let Y = ki=1 Yi . Assuming that
Eibad does not occur for each i ∈ [1, k], it follows that X −Y is a lower bound on the number of happy
vertices. Notice that by Lemma 11, Pr[Eibad ] = exp(−Ω(|Qi |)) = exp(−Ω(∆)). Thus, assuming
that no Eibad occurs merely distorts our probability estimates by a negligible exp(−Ω(∆)). We
prove concentration bounds on X and Y , which together imply the lemma.
We show that X ≥ pǫ∆/7 with probability 1 − exp(−Ω(ǫ∆)). It is clear that
Pr[Xi = 1] ≥ Pr[Eigood | Eibad ] ≥
14

p(1 − ǫ/2)
p
p · |Qi |/2
≥
> .
∆+1
2
3

Moreover, since Pr[Xi = 1 | Eibad ] = 1, the above inequality also holds, when conditioned on any
colors selected by vertices in Ri . Thus, Pr[X ≤ t] is upper bounded by Pr[Binomial(n′ , p′ ) ≤ t] with
n′ = |S| = ǫ∆/2 and p′ = p3 . We set t = pǫ∆/7. Notice that n′ p′ = pǫ∆/6 > t. Thus, according to
2

) = exp(−Ω(ǫ∆)).
a tail bound of binomial distribution, Pr[X ≤ t] ≤ exp( −(n2np′ p−t)
′
′ ′

We show that Y ≤ pǫ2 ∆/2 with probability 1 − exp(−Ω(ǫ2 ∆)). It is clear that Pr[Yi = 1] ≤
≤ pǫ
2 , even if we condition on arbitrary colors selected by vertices in {u1 , . . . , ui−1 }. We have

p(i−1)
∆+1

2

pǫ ∆
2
µ = E[Y ] ≤ pǫ
2 · |S| =
4 . Thus, by a Chernoff bound (with δ = 1), Pr[Y ≥ pǫ ∆/2] ≤ Pr[Y ≥
2
2
(1 + δ)µ] ≤ exp(−δ µ/3) = exp(−Ω(ǫ ∆)).

To summarize, with probability at least 1 − exp(−Ω(ǫ2 ∆)), we have X − Y ≥ pǫ∆/7 − pǫ2 ∆/2 >
pǫ∆/8.
Lemma 13 considers the case when a large fraction of v’s neighbors are likely to color themselves
with colors outside the palette of v, and therefore be counted by f1 (v). This lemma holds regardless
of whether v is ǫ-sparse or not.

Lemma 13. Suppose that there is a subset S ⊆ N (v) such that |S| = ǫ∆/5, and for each u ∈ S,
2
Ψ(u) \ Ψ(v) ≥ ǫ(∆ + 1)/5. Then f1 (v) ≥ pǫ100∆ with probability at least 1 − exp(−Ω(ǫ2 ∆)).
Proof. Let S = (u1 , . . . , uk ) be sorted in increasing order by ID. Define Ri = N ∗ (ui ), and Qi =
Ψ(ui ) \ Ψ(v). Notice that |Qi | ≥ ǫ∆/5. Define the following events.
Eigood : ui selects a color c ∈ Qi and c is not selected by any vertex in Ri .
Eibad : the number of colors in Qi that are selected by vertices in Ri is more than |Qi |/2.
P
Let Xi be the indicator random variable that either Eigood or Eibad occurs, and let X = ki=1 Xi .
Given that the events Eibad for all i ∈ [1, k] do not occur, we have X ≤ f1 (v), since if Eigood occurs,
then ui successfully colors itself by some color c ∈
/ Ψ(v). By Lemma 11, Pr[Eibad ] = exp(−Ω(|Qi |)) =
exp(−Ω(ǫ∆)). Thus, up to this negligible error, we can assume that Eibad does not occur, for each
i ∈ [1, k]. We now show that X ≥ ǫ2 ∆/100 with probability 1 − exp(−Ω(ǫ2 ∆)).
pǫ
i |/2
It is clear that Pr[Xi = 1] ≥ Pr[Eigood | Eibad ] ≥ p|Q
∆+1 ≥ 10 , and therefore this inequality
holds even when conditioning on arbitrary colors selected by vertices in Ri . Thus, Pr[X ≥ t] is
′ ′
pǫ
. We set t = n2p =
upper bounded by Pr[Binomial(n′ , p′ ) ≤ t] with n′ = |S| = ǫ∆/5 and p′ = 10
pǫ2 ∆
100 . Thus, according to our bound
′ ′
2
) = exp(−Ω(ǫ2 ∆)).
exp( −(n2np′ p−t)
′

on the lower tail of the binomial distribution, Pr[X ≤ t] ≤

Lemma 14 considers the case that many pairs of neighbors of v are likely to color themselves
the same color, and contribute to f2 (v). Note that any ǫ-sparse vertex that does not satisfy the
preconditions of Lemma 13 does satisfy the preconditions of Lemma 14.
Lemma 14. Let v be an ǫ-sparse vertex. Suppose that there is a subset S ⊆ N (v) such that
|S| ≥ (1 − ǫ/5)∆, and for each u ∈ S, Ψ(u) ∩ Ψ(v) ≥ (1 − ǫ/5)(∆ + 1). Then f2 (v) ≥ pǫ2 ∆/2000
with probability 1 − exp(−Ω(ǫ2 ∆)).
ǫ∆
, (ii) each ui ∈ S ′ is associated with a set
Proof. Let S ′ be any subset of S such that (i) |S ′ | = 100
ǫ∆
′
′
Si ⊆ S \ (S ∪ N (ui )) of size 2 . The existence of S , S1 , . . . , S|S ′ | is guaranteed by the ǫ-sparseness
of v. In particular, S must contain at least ǫ∆ − ǫ∆/5 > ǫ∆/100 = |S ′ | non-friends of v, and for
each such non-friend ui ∈ S ′ , |S \ (S ′ ∪ N (ui ))| ≥ ∆(1 − ǫ/5 − ǫ/100 − (1 − ǫ)) > ǫ∆/2.

15

Order the set S ′ = {u1 , . . . , uk } in increasing order by vertex ID. Define Ri = {u1 , . . . , ui−1 } ∪
N ∗ (ui ), and Qi = Ψ(ui ) ∩ Ψ(v). Define Qgood
as the subset of colors c ∈ Qi such that c is selected
i
by some vertex w ∈ Si , but c is not selected by any vertex in (N ∗ (w) ∪ N ∗ (ui )) \ S ′ ). Define the
following events.
Eigood : ui selects a color c ∈ Qgood
.
i
Eibad : the number of colors in Qgood
is less than pǫ∆/8.
i
Eirepeat : the color selected by ui is also selected by some vertices in {u1 , . . . , ui−1 }.
P
Let Xi be the indicator random variable that either Eigood or Eibad occurs, and let X = ki=1 Xi .
P
Let Yi be the indicator random variable that Eirepeat occurs, and let Y = ki=1 Yi . Suppose that
Eigood occurs, and the color c selected by ui is not selected by any vertex in S \ {ui }. Then there
must exist a vertex w ∈ Si such that both ui and w successfully color themselves c. Notice that w
and ui are not adjacent. Thus, X − Y ≤ f2 (v), given that Eibad does not occur, for each i ∈ [1, k].
Notice that Pr[Eibad ] = exp(−Ω(ǫ2 ∆)) (by Lemma 12 and the definition of Qgood
), and thus indeed
i
bad
we can assume that Ei does not occur. In what follows, we prove concentration bounds on X
and Y , which together imply the lemma.
2

∆
2
We show that X ≥ pǫ
1000 with probability 1 − exp(−Ω(ǫ ∆)). It is clear that Pr[Xi = 1] ≥
pǫ∆/8
pǫ
∆+1 < 8 regardless of the colors selected by vertices in Ri . Thus, Pr[X ≤ t] is upper bounded by

Pr[Binomial(n′ , p′ ) ≤ t] with n′ = |S ′ | =

ǫ∆
100

pǫ
pǫ2 ∆
′ ′
8 . We set t = 1000 < n p .
−(n′ p′ −t)2
exp( 2n′ p′ ) = exp(−Ω(ǫ2 ∆)).

and p′ =

tail bound of binomial distribution, Pr[X ≤ t] ≤

According to a

2

∆
2
We show that Y ≤ pǫ
2000 with probability 1 − exp(−Ω(ǫ ∆)). It is clear that Pr[Yi = 1] ≤
p(i−1)
pǫ
∆+1 ≥ 100 regardless of the colors selected by vertices in {u1 , . . . , ui−1 }. We have µ = E[Y ] ≤
2

pǫ ∆
· |S ′ | = 10,000
. Thus, by a Chernoff bound (with δ = 4), Pr[Y ≥
exp(−δµ/3) = exp(−Ω(ǫ2 ∆)).
pǫ
100

pǫ2 ∆
2000 ]

≤ Pr[Y ≥ (1 + δ)µ] ≤

To summarize, with probability at least 1 − exp(−Ω(ǫ2 ∆)), we have X − Y ≥ pǫ2 ∆/1000 −
> pǫ2 ∆/2000.

pǫ2 ∆/2000

Lemma 15. The number of vertices in N (v) that remain uncolored after OneShotColoring is at least
(1 − 1.1p)|N (v)|, with probability at least 1 − exp(−Ω(|N (v)|)).
Proof. Let X be the number of vertices in N (v) participating in OneShotColoring. It suffices to
show that X ≤ 1.1p|N (v)| with probability 1 − exp(−Ω(|N (v)|)). Since a vertex participates with
2
(v)|
) = exp(−Ω(|N (v)|)) (by
probability p, we have Pr[X ≥ (1 + 0.1)p|N (v)|] ≤ exp(− (0.1) p|N
3
Chernoff bound with δ = 0.1). Thus, we conclude the lemma.

C

Analysis of ColorBidding — Proof of Lemma 10

Consider a directed acyclic graph G = (V, E), where each vertex v has a palette Ψ(v). Recall that
each vertex v is associated with a parameter pv ≥ |Ψ(v)| − outdeg(v), and we write p⋆ = minv∈V pv .
The maximum
out-degree is denoted as d⋆ . There is aPnumber C > 0 such that all vertices v
P
satisfy
u∈Nout (v) 1/pu ≤ 1/C. Intuitively, the term
u∈Nout (v) 1/pu measures the amount of
“contention” at a vertex v (in ColorBidding, u selects each color c ∈ Ψ(u) with probability 2pCu ,
which is proportional to 1/pu ). All vertices agree on the value of C.
16

ColorBidding. Each color c ∈ Ψ(v) is added to Sv with probability 2pCv independently. If there
exists a color c⋆ ∈ Sv that is not selected by all vertices in Nout (v), v colors itself c⋆ .
In Lemma 16 we present an analysis of ColorBidding. We show that after an iteration of ColorBidding, the amount of “contention” at a vertex v decreases by (roughly) an exp(C/6)-factor, with
very high probability. See [11, 28, 7] for proofs of similar claims. The main technical difficulty of
our setting is that we need to deal with vertices with different out-degrees, and the guarantee of
the number of excess colors of a vertex depends on its out-degree (rather than the global parameter
∆), and so we cannot simply use out-degree as the measure of contention.
Lemma 16. Consider an execution of ColorBidding. Let v be any vertex. Let d be the summation
of 1/pu over all vertices u in Nout (v) that remain uncolored after ColorBidding. Then the following
holds.
Pr[ v remains uncolored ] ≤ exp(−C/6) + exp(−Ω(p⋆ )).


Pr[d ≥ (1 + λ) exp(−C/6)/C] ≤ exp −2λ2 p⋆ exp(−C/6)/C + d⋆ exp(−Ω(p⋆ )).

Proof. For each vertex u, we define the following two events.

Eugood : u selects a color that is not selected by any vertex in Nout (u).
Eubad : number of colors in Ψ(u) that are selected by some vertices in Nout (u) is at least

2
3

· |Ψ(u)|.

Notice that Eugood is the event where u successfully colors itself. We show that Pr[Eubad ] =
exp(−Ω(p⋆ )). Fix a color c ∈ Ψ(u). The probability that c is selected by some vertex in Nout (u) is

X
Y 
C
1
1−
1 − 2pCu ≤
2pu ≤ 2 .
u∈Nout (v)

u∈Nout (v)

′

Thus, Pr[Eubad ] ≤ Pr[Binomial(n′ , p′ ) ≥ 2n3 ] with n′ = |Ψ(u)| ≥ pu and p′ =
bound, we have:
Pr[Eubad ] ≤ exp(−Ω(n′ p′ )) = exp(−Ω(p⋆ )).

1
2.

By a Chernoff

Conditioned on Eubad , u will color itself unless it fails to choose any of |Ψ(u)|/3 specific colors from
its palette. Thus,





Pr[Eugood | Eubad ] ≤ 1 − 2pCu |Ψ(u)|/3 ≤ 1 − 2pCu pu /3 ≤ exp −C
6 .
We are now in a position to prove the first inequality. The probability that v remains uncolored
⋆
is at most Pr[Eibad ] + Pr[Eugood | Eubad ], which is at most exp( −C
6 ) + exp(−Ω(p )).

Next, we prove the second inequality. Let Nout (v) = (u1 , . . . , uk ) sorted in reverse topological
order. Let Eibad and Eigood be short for Eubad
and Eugood
. Notice that Nout (ui ) ∩ {ui , . . . , uk } = ∅,
i
i
and so by a union bound,
#
" k
[
bad
≤ outdeg(v) · exp(−Ω(p⋆ )) ≤ d⋆ · exp(−Ω(p⋆ )).
Ei
Pr
i=1

17

Let Xi = 1/pui if either Eigood or Eibad occurs, and Xi = 0 otherwise. Let X =
that if Eibad does not occur, for all i ∈ [1, k], we have X = d.
def

Pk

i=1 Xi .

Notice

Each variable Xi
Observe that µ = E[X] ≤ exp(−C/6)/C, since Pr[Eigood | Eibad ] ≤ exp( −C
6 ). P
Pk
2
is within the range [ai , bi ], where ai = 0 and bi = 1/pui . We have i=1 (bi −ai ) ≤ u∈Nout (v) 1/(pu ·
p⋆ ) ≤ 1/(Cp⋆ ). By Hoeffding’s inequality, we have
Pr[X ≥ (1 + λ) exp(−C/6)/C] ≤ Pr[X ≥ (1 + λ)µ]
≤ exp

−2(λµ)2

Pk

i=1 (bi

− ai )2

!


≤ exp −2(λ exp(−C/6)/C)2 (p⋆ C)

= exp −2λ2 p⋆ exp(−C/6)/C .

Thus, Pr[d ≥ (1 + λ) exp(−C/6)/C] ≤ exp −2λ2 p⋆ exp(−C/6)/C + d⋆ exp(−Ω(p⋆ )).

Proof of Lemma 10. In what follows, we show how Lemma 16 can be used to derive Lemma 10. Our
plan is to apply ColorBidding for O(log∗ (p⋆ )) iterations. For the ith iteration we use the parameter
√
Cl−1
Ci , which is defined as follows: C1 = C, and Cl = min{ p⋆ ,
−Cl−1 }. Here λ must be
(1+λ) exp(

6

)

selected to be sufficiently small such that (1 + λ) exp(−Cl−1 /6) < 1 so the sequence increases. For
example, if C ≥ 6 initially, we can fix λ = 1 throughout.
In each iteration each vertex v use the same parameter pv , since the number of excess colors
√
never decrease. The last iteration l⋆ = O(log∗ (p⋆ )) is the minimum index l such that Cl = p⋆ .
At the end of the lth iteration (1 ≤ l ≤ l⋆ ), we have the following invariants Hl that we expect
all vertices to satisfy: If 1 ≤ l < l⋆ , for each uncolored vertex v after the lth iteration, we require
the summation of 1/pu over all uncolored vertices u in Nout (v) to be less than 1/Cl+1 ; if l = l⋆ , all
vertices are colored at the end of the lth iteration. The purpose of the invariant Hl (1 ≤ l < l⋆ ) is
to guarantee that the parameter Cl+1 is a valid parameter for the (l + 1)th iteration.
We remove from consideration all vertices v violating Hl at the end of the lth iteration, and
√
add them to the set Vbad . Our goal is to show that with probability at most exp(−Ω( p⋆ )) +
d⋆ exp(−Ω(p⋆ )), a vertex v is removed, and this is true even if the randomness outside constant
distance to v is determined adversarially. By definition of Hl⋆ , all vertices that are not removed
must be colored.
By Lemma 16 the probability that a vertex v is removed at the end of the lth iteration, where
√
1 ≤ l < l⋆ , is at most exp(Ω(p⋆ /Cl+1 )) + d⋆ exp(−Ω(p⋆ )) ≤ exp(−Ω( p⋆ )) + d⋆ exp(−Ω(p⋆ )); and
the probability that a vertex v is removed at the end of the l⋆ th iteration is at most exp(−Cl⋆ /6) +
√
exp(−Ω(p⋆ )) ≤ exp(−Ω( p⋆ )).

D

Coloring ǫ-Dense Vertices

Consider the following setting. We are given a graph G = (V, E), where a subset of vertices are
already colored. Let S be a subset of the uncolored vertices, and suppose S is partitioned into g
disjoint sets (clusters) S1 , . . . , Sg , each with weak diameter 2. Our goal is to color a large fraction
of the vertices in S in only constant time.
In Section D.1 we describe a procedure DenseColoringStep (version 1) that is efficient when each
vertex has many excess colors w.r.t. S. It is analyzed in Lemma 17, which is then used to prove
Lemmas 6 and 7. In Section D.2 we describe a procedure DenseColoringStep (version 2), which is

18

a generalization of the procedure introduced by Harris, Schneider, and Su [18]. It is analyzed in
Lemma 18, which is then used to prove Lemmas 8 and 9.
The proof of Lemma 17 is straightforward and appears immediately after its statement. The
proof of Lemma 18 is deferred to Section D.3.

D.1

Version 1 — Many Excess Colors are Available

All vertices in S agree on a parameter Zex , which is a lower bound on the number of excess colors
w.r.t. S. That is, for each v ∈ S, the palette size of v minus the number of neighbors of v in S is
at least Zex .
Each vertex v ∈ Sj is associated with a parameter Dv . We prioritize vertices by Dv -value,
breaking ties by ID. Define N ′ (v) = {u ∈ N (v) | Du < Dv or Du = Dv and ID(u) < ID(v)} to be
the neighbors of v with higher priority. If v ∈ Sj , the parameter Dv must satisfy |N ′ (v) ∩ (S \ Sj )| ≤
Dv . Define δv = Dv /Zex .
DenseColoringStep (version 1)
1. Let π : {1, . . . , |Sj |} → Sj be the permutation that lists Sj in increasing order by D-value,
breaking ties by ID. For q from 1 to |Sj |, the vertex π(q) selects a color c(π(q)) uniformly
at random from Ψ(π(q)) \ {c(π(q ′ )) | q ′ < q and {π(q), π(q ′ )} ∈ E(G)}.
2. Each v ∈ Sj permanently colors itself c(v) if c(v) is not selected by any vertices in N ′ (v).
Observe that because each Sj has weak diameter 2, Step 1 of DenseColoringStep takes only
O(1) rounds of communication. Intuitively, the probability that a vertex v ∈ S remains uncolored
after DenseColoringStep (version 1) is at most δv . The following lemma gives us the probabilistic
guarantee of the DenseColoringStep (version 1).
Lemma 17. Consider an execution of DenseColoringStep (version 1). Let T be any subset of S,
and let δ = maxv∈T δv . For any t, the number of uncolored vertices in T is at least t with probability
at most Pr[Binomial(|T |, δ) ≥ t].
Proof. Let T = {v1 , . . . , v|T | } be listed by priority: in increasing order by D-value, breaking ties
by vertex ID. (Remember that vertices in T can be spread across multiple clusters in S.) Imagine
exposing the color choices of all vertices in S, one by one, in order of priority. The vertex vl will
successfully color itself if it chooses any color not already selected by a vertex in N ′ (vl ) ∩ (S \ Sj ).
Since |N ′ (vl ) ∩ (S \ Sj )| ≤ Dv and vl has at least Zex colors to choose from, the probability that it
fails to be colored is at most Dv /Zex = δv ≤ δ, independent of the choices made by higher priority
vertices. Thus, for any t, the number of uncolored vertices in T is at least t with probability at
most Pr[Binomial(|T |, δ) ≥ t].
Next, we prove Lemmas 6 and 7. The basic setup of these two proofs are similar. We let
S = WkS (k = 1 for Lemma 7), and let S1 , . . . , Sg be the super -blocks constituting S. According
to Lemma 2 we can set Zex = ∆/2 log2 (1/ξk ) and according to Lemma 1’s bound on the external
degree we can set Dv = ǫi ∆ if v is a layer-i vertex. Our algorithm consists of several iterations of
DenseColoringStep (version 1) on S = S1 ∪ · · · ∪ Sg .

19

D.1.1

Proof of Lemma 6

We execute DenseColoringStep (version 1) for 6 iterations using the same parameters Zex and Dv
for all iterations. Consider any vertex v ∈ V ⋆ , and a layer i that is within stratum k. Let T be the
∆
= 2ǫi log2 (1/ξk ) ≤ 2ǫi log2 (1/ǫi ).
set of layer-i neighbors of v in S. Then δ = maxu∈T {δu } ≤ ǫZiex
Define t0 = |T |, and tl = max{2δtl−1 , ǫ5i ∆}. Since (2δ)6 |T | ≤ ǫ5i ∆, we have t6 = ǫ5i ∆.
Assume that at the beginning of the lth iteration, the number of uncolored vertices in T is at
most tl−1 . By Lemma 17 and a Chernoff bound, after the lth iteration, with probability at most
exp(−Ω(tl )) ≤ exp(−Ω(ǫ5i ∆)), the number of uncolored vertices in T is more than tl . Thus, with
probability 1 − exp(−Ω(poly(∆))), after 6 iterations the number of uncolored layer-i neighbors of v
in WkS is at most ǫ5i ∆.
D.1.2

Proof of Lemma 7

Notice that the parameter δv = Dv /Zex is always at most 2ǫ1 log2 (1/ǫ1 ) ≪ ∆−1/20 . Thus, we define
δ̄ = ∆−1/20 as an upper bound on δv . Let x be a number to be determined. Consider the following
invariants that all vertices v ∈ S and all clusters Sj should satisfy after the lth iteration:
Invariant Hl (v): the number of uncolored vertices of (N (v) ∩ S) is at most max{x, δ̄l ∆}.
Invariant Hl (Sj ): the number of uncolored vertices of Sj is at most max{x, δ̄l ∆}.
⋆

Let l⋆ be minimum such that δ̄l ∆ ≤ x. We run DenseColoringStep (version 1) for l⋆ iterations.
Again, we use the same parameters Zex and Dv (as defined above). Via Lemma 17, it is straightforward to prove the following probabilistic bounds using a Chernoff bound.
Pr[H1 (v)] = 1 − exp(−Ω(poly∆)).

Pr[Hl (v) | Hl−1 (v)] = 1 − exp(−Ω(x)), for 1 < l ≤ l⋆ .
Pr[H1 (Sj )] = 1 − exp(−Ω(poly∆)).

Pr[Hl (Sj ) | Hl−1 (Sj )] = 1 − exp(−Ω(x)), for 1 < l ≤ l⋆ .
For any l ∈ [1, l⋆ ], any uncolored vertex v ∈ Sj such that Hl (v) or Hl (Sj ) is violated is removed
from further consideration at the end of the lth iteration, and included in Vbad . Thus, by the end
of the l⋆ th iteration, we have x as an upper bound on the cluster size and the maximum degree of
the remaining uncolored vertices.
Case: ∆ = O(log4 n). For this case, we set x = ∆1/20 . We do one additional iteration of
DenseColoringStep (version 1), aiming to reduce the maximum degree of the uncolored vertices to
O(1). For this iteration, we set Dv = ∆1/20 , and Zex = ∆/2 log2 (1/ξ1 ) = Θ(∆/ log2 ∆). Thus, we
have the shrinking rate δv = O(∆−19/20 log2 ∆).
Let v ∈ S be any vertex. By Lemma 17, the probability that there exists at least t uncolored neighbors of v in S is at most Pr[Binomial(|T |, δ) ≥ t], where |T | = ∆1/20 and δ =
O(∆−19/20 log2 ∆). Thus, Pr[Binomial(|T |, δ) ≥ t] ≤ |T |t δt = ∆−Ω(t) .
Case: ∆ = Ω(log4 n). We now turn to the case where ∆ = Ω(log4 n). We set x = Θ(log n).
Clearly, with high probability (i.e., 1 − 1/poly(n)) all invariants H1 (v) and H1 (Sj ) are met for each
iteration. But we still need to reduce the maximum degree from Θ(log n) to O(1).
We do DenseColoringStep (version 1) for one extra iteration. This time, for each vertex v, we
use the parameter
Dv = D = x = Θ(log n), and so the shrinking rate is δv = δ = D/Zex =

log n
O ∆/ log2 ∆ ≪ 1/ log 2 n, due to the assumption ∆ = Ω(log4 n).
20

Consider any uncolored vertex v, and let T be the set of uncolored neighbors of v just before
this iteration. Notice that |T | ≤ x = O(log n). By Lemma 17, after this iteration, the number of
uncolored vertices in T is at least t with probability at most Pr[Binomial(|T |, δ) ≥ t] ≤ |T |t δt =
(O(1/ log n))t . After this iteration, we partition the uncolored vertices into two subsets X and R,
where X consists of all vertices whose number of uncolored neighbors are at least t. Thus, the
subgraph induced by R has maximum degree O(1).
Using Lemma 4, we argue that if t is set to be sufficiently large, then vertices in X form connected
components of size at most poly log n, with high probability. Consider the graph G′ induced by the
vertices that are uncolored at the beginning of this iteration, together with additional edges added to
G′ making (the uncolored vertices of) each cluster a clique. Due to the O(log n) upper bound on the
maximum degree and the cluster size, the maximum degree of G′ is also ∆′ = O(log n). Recall that a
vertex v is added to X with probability at most (O(1/ log n))t , and this is true regardless of random
bits of vertices outside of a constant radius of v in G′ . Thus, if t is a sufficiently large constant,
then w.h.p., each connected component of X in G′ has size at most O(poly(∆′ ) · log n) = poly log n.
Thus, w.h.p., each connected component of X (in the original graph G) has size poly log n.
Notice that in the above analysis, to argue that the component size is small, it is crucial that we
use Lemma 4 w.r.t. a graph whose maximum degree is poly log n, and this is the reason that we define
the graph G′ . This also explains the reason for having a separate set X (rather than adding all these
vertices to Vbad ). In general, the size of a component in Vbad ∪ X could be super-polylogarithmic.

D.2

Version 2 — No Excess Colors are Available

In this section we consider the case where there is no guarantee on the number of excess colors. In
this scenario, the palette size lower bound of each vertex v ∈ Sj comes from the assumption that
|Sj | is large, and v is adjacent to all but a very small portion of vertices in Sj . Each of the clusters
S1 , . . . , Sg has a unique ID (say the minimum ID of its constituents).
We assume each Sj is associated with parameters Dj and δj . For each v ∈ S, We define two
notions of neighborhood of a vertex.
• Ñ (v) is the set of vertices u ∈ N (v) ∩ S such that δj ′ ≤ δj and j 6= j ′ , where v ∈ Sj and
u ∈ Sj ′ .
• N ′′ (v) is the set of vertices u ∈ N (v) ∩ S such that (i) δj ′ < δj or (ii) δj ′ = δj and ID(Sj ) <
ID(Sj ′ ), where v ∈ Sj and u ∈ Sj ′ . Notice that N ′′ (v) ⊆ Ñ (v).

We assume that the parameters Dj and δj satisfy the following conditions.

• For each v ∈ Sj , we have |Sj \ (N (v) ∪ {v})| ≤ Dj , and |N ′′ (v)| ≤ Dj .

• δj must be at least

Dj log(|Sj |/Dj )
,
|Sj |

and δj ≤ 1/K for some large enough constant K.

The procedure DenseColoringStep (version 2) aims to successfully color a large (≈ 1 − δj ) fraction
of the vertices in each Sj .
DenseColoringStep (version 2).
1. Each cluster Sj selects (1 − δj )|Sj | vertices u.a.r. and generates a permutation π of those
vertices u.a.r. The vertex π(q) selects a color c(π(q)) u.a.r. from
Ψ(π(q)) − {c(π(q ′ )) | q ′ < q and {π(q), π(q ′ )} ∈ E(G)}.
2. Each v ∈ Sj that has selected a color c(v) permanently colors itself c(v) if c(v) is not
selected by any vertices u ∈ N ′′ (v).
21

Notice that the number of uncolored vertices in Sj after an execution of DenseColoringStep (version 2) is always at least δj |Sj |. Lemma 18 gives a probabilistic guarantee for this algorithm. Refer
to Appendix D.3 for proof.
Lemma 18. Consider an execution of DenseColoringStep (version 2). Let T be any subset of S,
and let δ = maxj:Sj ∩T 6=∅ δj . For any number t, the probability that the number of uncolored vertices

in T is at least t is at most |Tt | · (O(δ))t .
Next, we prove Lemmas 8 and 9. In what follows, DenseColoringStep refers to version 2.

D.2.1

Basic Setup

The proofs of Lemmas 8 and 9 are based on the following framework. Let S = W ′ (for Lemma 8)
or S = W1L (for Lemma 9). Let S1 , . . . , Sg be the blocks constituting S. Each Sj is a large block in
some layer. In subsequent discussion, the term anti-degree of v refers to the number of uncolored
vertices in Sj \ (N (v) ∪ {v}), and the term external degree of v refers to the number of uncolored
vertices in Ñ (v).
We execute DenseColoringStep for a number of iterations, to be determined shortly. At the end
of the lth iteration, we set the following invariants for each cluster Sj , which is a layer-i block. Let
β > 0 be a constant to be determined.
(l+1)

Invariant Hl (v): Both the anti-degree of v and the external degree of v are at most Dj
(l+1)

Invariant Hl (Sj ): the number of uncolored vertices of Sj is at least Zj


(1)
(l)
(l−1)
(l−1)
(l)
· Dj
, for l > 1.
Sequence Dj : Dj = 3ǫi ∆, and Dj = βδj


(1)
(l)
Sequence Zj : Zj =

∆
,
log2 (1/ǫi )

(l)

(l−1)

and Zj = δj

(l−1)

· Zj

(l)

.

.

, for l > 1.
(l)

The parameter Dj for the lth iteration is Dj . The parameter Zj indicates a cluster size lower
bound for Sj (i.e., the number of uncolored vertices in Sj at the beginning of the lth iteration is at
(l)

(l)

(l)

least Zj ). The shrinking rate δj for the lth iteration is always set to

(l)

(l)

Dj log(Zj /Dj )
(l)

Zj

.
(l)

(l)

Notice that if we initially have δj ′ ≤ δj for two clusters Sj and Sj ′ , then we have δj ′ ≤ δj for
all iterations l. Thus, the definitions of Ñ (v) and N ′′ (v) remain unchanged. We have δj ′ < δj if
and only if the layer-number of Sj ′ is smaller than the layer-number of Sj ; and δj ′ = δj if and only
Sj and Sj ′ are of the same layer.
(1)

Validity of Parameters. The parameter Dj for the first iteration is valid due to Lemma 1’s
bounds on the external degree (at most ǫi ∆) and anti-degree (at most 3ǫi ∆) of a vertex in an ǫi ∆
≥ log2∆
is the lower bound on the size of a stratum-k, layer-i
almost clique. Recall that log2 (1/ξ
)
(1/ǫ )
k

large block. Thus, we must have |Sj | ≥

i

∆
,
log2 (1/ǫi )

(1)

and so Zj

(l)

is a lower bound for |Sj |. Therefore,

the shrinking rate δj for l = 1 is valid. The validity of parameter choices in the lth iteration, l > 1,
follows from the invariants for the (l − 1)th iteration.

22

Maintenance of Invariants. We calculate the probability for the invariant Hl (v) to be met,
where v ∈ Sj . For the case of l > 1, the probability is conditioned on Hl−1 (Sj ) and Hl−1 (u) holding

 
(l) t
for all remaining uncolored u ∈ Sj . By Lemma 18, we have Pr[Hl (v)] ≥ 1 − |Tt | · O(δj ) ,
(l)

(l+1)

(l)

(l)

with |T | ≤ Dj and t = Dj
= βδj · Dj . If we select β to be a large enough constant, then

t 
t

(l)
(l)
(l+1)
(l+1)
|T |
·
O(δ
)
≤
O(δ
)
·
e|T
|/t
= exp(−Ω(Dj
)). Thus, Pr[Hl (v)] ≥ 1 − exp(−Ω(Dj
)).
j
j
t
Each vertex v that fails to satisfy Hl (v) at the end of the lth iteration is removed from consideration and added to Vbad . Ordinarily the invariant Hl (Sj ) always holds (by inspection of the
procedure DenseColoringStep); however, when we remove a vertex v ∈ Sj that violate Hl (v), this
may cause Hl (Sj ) to be violated. In this case, we also remove all uncolored vertices in Sj from
further consideration and put them all in Vbad .
D.2.2

Proof of Lemma 8

We perform 6 iterations ofDenseColoringStep.
For
layer i, a simple calculation that

 acluster Sj inQ
 
(l)
(l)
(l)
(l)
shows that 6l=1 δj = ǫ6i poly log(1/ǫi ) ≪ ǫ5i .
uses only the definition of Dj , Zj , and δj
(l+1)

Recall the probability for an invariant Hl (v) to be violated is exp(−Ω(Dj
)) = exp(−Ω(poly(∆))),
for the range 1 ≤ l ≤ 6.
Consider any vertex v ∈ V ⋆ , and a layer i, with i ∈ [2, ℓ]. Let T be the set of layer-i neighbors
(l)
of v in S. Define t0 = |T |, and tl = max{βδj tl−1 , ǫ5i ∆} (the cluster Sj is in layer i). We have
t6 = ǫ5i ∆.
Assume that at the beginning of the lth iteration, the number of uncolored vertices in T is at
most tl−1 . By Lemma 18, after the lth iteration, the number of uncolored vertices in T is more than
tl with probability at most



tl−1 
(l) tl
· O(δj ) ≤ exp(−Ω(tl )) ≤ exp(−Ω(ǫ5i ∆)).
tl

Thus, with probability 1 − exp(−Ω(poly(∆))), the number of uncolored layer-i neighbors of v in
S = W ′ is at most ǫ5i ∆.
D.2.3

Proof of Lemma 9
(l)

(l)

In the setting of Lemma 9, we deal with only layer-1 large blocks, and so D1 = . . . = Dg
(l)
(l)
and Z1 = . . . = Zg , for all indices l. For this reason we drop the subscripts. Notice that
Ñ (v) = N (v) \ Sj for each v ∈ Sj , since all clusters Sj use the same parameter δ = δj
The proof consists of three parts. The set R is generated during Part 3. For the case of
∆ ≤ logα n case, each vertex v ∈ S is colored or joins R with probability 1 − exp(−Ω(poly(∆)));
with probability exp(−Ω(poly(∆))), v joins Vbad . For the ∆ ≥ logα n case, the set X1 is generated
in Part 2, and the set X2 is generated in Part 3. W.h.p., each vertex v ∈ S is either colored, or
joins one of R, X1 , X2 .
Part 1 — Basic Steps. We first do 9 iterations of DenseColoringStep.
Due

 to the(l)fact
 that
−1/10
(l)
(l)
ǫ1 = ∆
, a simple calculation (which uses only the definition of D , Z , and δ ) shows
that D (10) = poly log(∆) and Z (10) = ∆1/10 poly log(∆).
For each of these iterations, we set an additional invariant Il (Sj ) regarding cluster size upper
bounds. At the end of the lth iteration, we require that the number of uncolored vertices in each
23

Q
cluster Sj is at most 2∆· li=1 (βδ(i) ) = Z (l+1) ·O(log2 ∆) > Z (l+1) . (Initially |Sj | < (1+3ǫ1 )∆ < 2∆,
by Lemma 1, and the ith iteration reduces the size by a factor of βδ(i) . The O(log2 ∆) factor arises
here because Z (1) = ∆/ log2 (1/ǫ1 ) = Θ(∆/ log2 ∆).)
Similar to the calculation of Pr[Hl (v)], the probability that Il (Sj ) is violated, conditioned on
Il−1 (Sj ), is exp(−Ω(Z (l+1) · log2 ∆)) = exp(−Ω(poly(∆))), for 1 ≤ l ≤ 9. Vertices in the clusters
not meeting this invariant are removed from consideration in subsequent steps. Thus, after the 9th
iteration, the number of uncolored vertices in Sj is guaranteed to be within the range [Z (10) , Z (10) ·
O(log2 ∆)].
For the case of ∆ ≥ logα n, we have an additional special step, which is one extra iteration of
c
n
DenseColoringStep with shrinking rate δ = log
, for some constant c to be determined. This step
(10)
Z
has two purposes: to reduce the cluster size to the range [logc n, logc n · O(log2 ∆)], and to reduce
the anti-degree and external degree upper bound to O(log n).
With high probability, the above criteria are met everywhere. For instance, consider a cluster
Sj . Before this additional special step, the number of uncolored vertices in Sj is already at most
Z (10) · C log2 ∆, for some constant C. By Lemma 18, the probability that the number of uncolored
vertices in Sj is at least t = logc n · βC log2 ∆ is at most
!t
 c 
 (10)
   c t
log n
e · Z (10)
Z
· C log2 ∆
log n
≤ O
·
= exp(−Ω(t)) < 1/poly(n),
· O
logc n · β
t
Z (10)
Z (10)
if β is a large enough constant. Similarly, one can show that, w.h.p., after the additional special
step, the anti-degree and external degree of each vertex is at most O(log n).
We summarize properties that all vertices and all clusters satisfy at the end of Part 1. For the
∆ ≤ logα n case, the anti-degree and external degree upper bound is D (10) = poly log(∆), and the
cluster size lower bound is Z (10) = ∆1/10 poly log(∆). For the ∆ ≥ logα n case, the anti-degree
and external degree upper bound is O(log n), and the cluster size lower bound is logc n. In both
cases, we have a cluster size upper bound that is within an O(log2 ∆)-factor of the cluster size lower
bound. All vertices and all clusters use the same bounds.
Part 2 — Reducing External Degree and Anti-degree to O(1). Next, we do one extra
iteration of DenseColoringStep with shrinking rate δ defined as follows. For the case ∆ ≤ logα n, we
use δ = ∆−1/20 ; for the case of ∆ ≥ logα n, we use δ = 1/ logc/2 n. We fix x to be some sufficiently
large constant and analyze the probability that the external and anti-degree of a vertex are both at
most x. That is, the number of uncolored vertices in both Sj \ (N (v) ∪ {v}) and N ′′ (v) are at most
x.
Case: ∆ ≤ logα n. By Lemma 18, the probability that the external or anti-degree of v ∈ Sj is at
most x is:


 (10) 
x
poly log(∆) 
D
x
O(∆−1/20 ) ≥ 1 − ∆−Ω(x) .
(O(δ)) ≥ 1 −
1−
x
x

The vertices failing to satisfy this criterion are removed from consideration and added to Vbad . After
this iteration, we have ZLB = ∆1/20 poly log(∆) as the new cluster size lower bound. Similarly, we
impose a cluster size upper bound of ZUB = ZLB · O(log2 ∆) = ∆1/20 poly log(∆). All uncolored
vertices in a cluster Sj whose number of uncolored vertices is not within [ZLB , ZUB ] is removed from
consideration and added to Vbad . The probability that the number of uncolored vertices in Sj is
above ZUB is at most exp(−Ω(ZUB )) = exp(−Ω(poly(∆))). The calculation of this probability is via
Lemma 18 with |T | = Z (10) · O(log2 ∆) (cluster size upper bound at the beginning of this iteration)
24

and t = ZUB (the new cluster size upper bound). Notice that the cluster size lower bound ZLB is
automatically satisfied if no constituent vertex is removed.
Case: ∆ ≥ logα n. By Lemma 18, the probability that the external or anti-degree of v ∈ Sj is at
most x is:


x
c
O(log n) 
O(1/ log c/2 n) ≥ 1 − (O(1/ log n))( 2 −1)x ,
1−
x

We let X1 be the set of the vertices not meeting this criterion. If x is a large enough constant (not
depending on c), then according to Lemma 4, the vertices of X1 form connected components of size
at most O(poly(∆′ ) · log n), w.h.p., where ∆′ is the external degree upper bound plus the cluster
size upper bound at the beginning of this iteration. The proof is the same as the proof showing that
each connected component of X has size at most O(poly log n) in Lemma 7. Due to the previous
step that reduced the cluster size upper bound to O(logc n·log2 ∆), it is guaranteed that the vertices
of X1 form connected components of size poly log n.
After this iteration, we have ZLB = logc/2 n as the cluster size lower bound. We impose a cluster
size upper bound of ZUB = logc/2 n · O(log2 ∆). With high probability, all clusters Sj satisfy this
criterion (by Lemma 18 with |T | = logc n · O(log2 ∆) and t = logc/2 n · O(log2 ∆)). Thus, w.h.p.,
the number of uncolored vertices in each cluster Sj is within [ZLB , ZUB ] after this iteration.

Part 3 — Reducing the Maximum Degree to O(1). Finally, we do one more iteration of
DenseColoringStep with D = x = O(1) and shrinking rate δ = O((log ZLB )/ZLB ), where ZLB is the
current cluster size lower bound from Part 2.
We call a vertex bad if it is still uncolored and has at least one uncolored external neighbor after
this iteration. We will show that with a certain probability, the number of bad vertices in Sj is at
most some constant z.
Consider any size-z subset Y of Sj . By Lemma 18, the probability that all vertices in Y are bad
1
1
is at most xz · (O(δ))z(1+ x ) ≤ (O(δ))z(1+ x ) . The reason is as follows. If v ∈ Y is bad, then there
exists a vertex v ′ ∈ N (v) \ Sj that is uncolored.
There are at most xz ways of mapping each v ∈ Y
S
to a vertex v ′ ∈ N (v) \ Sj of v. Let T = v∈Y {v, v ′ }. A vertex outside of Sj can be adjacent to at
most x vertices in Sj , and so |T | ≥ z(1 + x1 ). The probability that all vertices in T are uncolored is
1

(O(δ))z(1+ x ) by Lemma 18. By a union bound over at most xz choices of T , we obtain the desired
probabilistic bound.
Recall that ZUB = ZLB · O(log2 ∆) is the cluster size upper bound at the beginning of this
iteration. By a union bound over at most (ZUB )z choices of a size-z subset of Sj , the probability
that there exists z bad vertices in Sj is:
z/x
z 
1
ZLB
)
(ZUB )z · (O(δ))z(1+ x ) = O(log ZLB log2 ∆) · O( logZLB
x z/x  log ZLB z/x
.
= O(log ZLB log2 ∆)
· O( ZLB )

For the ∆ ≤ logα n case, ZLB = ∆1/20 poly log(∆), and so the probability that Sj contains z
z/x

log ∆
)
= ∆−Ω(z) . For the ∆ ≥ logα n case, ZLB = logc/2 n, and so
bad vertices is O( poly
∆1/20
z/x

2x
log n)
)
= log−Ω(z) n. This last bound holds assuming the
the probability is O( log ∆·poly(log
logc/2 n
constant c is large enough relative to x, i.e., c/2 > 2x.
Lastly, in O(1) rounds, Sj permanently colors every uncolored vertex v ∈ Sj that has no uncolored
external neighbors. At this point, if we remove all bad vertices, the induced graph on the remaining
25

vertices, R, has bounded degree. For the case of ∆ ≤ logα n, all bad vertices join Vbad (just like
all vertices that violate an invariant). For the case of ∆ ≥ logα n, we let X2 be the set of all bad
vertices. By Lemma 4, w.h.p., these vertices form connected components of size at most poly log n.

D.3

Proof of Lemma 18

Throughout this section DenseColoringStep refers to version 2. Recall that in the DenseColoringStep
procedure, a vertex in Sj can remain uncolored for two different reasons: (i) it never selects a color,
because it is not among the (1 − δj )|Sj | selected vertices. or (ii) it selects a color, but is later
decolored because of a conflict with some vertex in Sj ′ with j ′ < j. Lemmas 19–21 analyze different
properties of DenseColoringStep, which are then applied to prove Lemma 18. Throughout we assume
δj < 1/K for some sufficiently large K.
Lemma 19. Let T = {v1 , . . . , vk } be any subset of Sj and c1 , . . . , ck be any sequence of colors. The
|T |
 
log(|Sj |/Dj )
.
probability that vi selects ci in DenseColoringStep, for all i ∈ [1, k], is O
|Sj |
Proof. Let p⋆ be the probability that, for all i ∈ [1, k], vi selects ci . Let L = (1 − δj )|Sj | be the
number of selected vertices. Notice that if vi is not among the selected vertices, then vi will not
select any color, and thus cannot select ci . Since we are upper bounding p⋆ , it is harmless to
condition on the event that vi is selected. We write pi to denote the rank of vi ∈ T in the random
permutation of Sj .
Suppose that the ranks p1 , . . . , pk were fixed. Recall that each vertex vi ∈ Sj is adjacent to all
but at most Dj vertices in Sj . Thus, at the time vi is considered it must have at least
L − pi + δj |Sj | − Dj ≥ L − pi + Dj log(|Sj |/Dj ) − Dj = (L − pi ) + Dj (log(|Sj |/Dj ) − 1)
available colors to choose from, at most one of which is ci . Thus,
#
" k
Y
1
.
p⋆ ≤ E
(L − pi ) + Dj (log(|Sj |/Dj ) − 1)
p1 ,...,pk
i=1

We divide the analysis into two cases: (i) k ≥ L/2 and (ii) k < L/2. For the case k ≥ L/2,
regardless of the choices of p1 , . . . , pk , we always have
k
Y
i=1

1
1
≤
= (O(1/k))k ≤ (O(1/|Sj |))|T | .
(L − pi ) + Dj (log(|Sj |/Dj ) − 1)
k!

We now turn to the case k < L/2. Regardless of the values of p1 , . . . , pi−1 , we always have

 PL−i
1
1
x=0 x+Dj (log(|Sj |/Dj )−1)
p1 , . . . , pi−1 ≤
E
((L − pi ) + Dj (log(|Sj |/Dj ) − 1)
L − (i − 1)
PL/2
1
≤

x=0 x+Dj (log(|Sj |/Dj )−1)

L/2

log L − log(Dj (log(|Sj |/Dj ) − 1))
=O
L


log(|Sj |/Dj )
=O
.
|Sj |


|T |
 
log(|Sj |/Dj )
, as claimed.
Therefore p⋆ ≤ O
|Sj |
26

Lemma 20. Let T be any subset of Sj . Even allowing the colors selected in S1 , . . . , Sj−1 be determined adversarially, the probability that all vertices in T are decolored in DenseColoringStep is at
|T |
 
Dj log(|Sj |/Dj )
.
most O
|Sj |
|T |

Proof. There are in total at most Dj different color assignments to T that can result in decoloring
all vertices in T , since each vertex v ∈ T ⊆ Sj satisfies |N ′′ (v)| ≤ Dj . By Lemma 19 (and a
|T |
union bound over Dj color assignments to T ) the probability that all vertices in T are decolored




Dj log(|Sj |/Dj ) |T |
|T |
log(|Sj |/Dj ) |T |
)
)
=
O(
.
is Dj · O(
|Sj |
|Sj |

Lemma 21. Let T be any subset of Sj . The probability that all vertices in T do not select a color
in DenseColoringStep is at most (O(δj ))|T | . The probability only depends on the random bits within
Sj .
Proof. The lemma follows from the fact that in DenseColoringStep a vertex v ∈ Sj does not select a
color with probability δj , and the events for two vertices u, v ∈ Sj to not select a color are negatively
correlated.
Proof of Lemma 18. In this proof, we assume that the clusters S = {S1 , . . . , Sg } are ordered by
prioritizing small δj values, breaking ties by cluster ID. That is, for any 1 ≤ j < j ′ ≤ g, either (i)
δj < δj ′ or (ii) δj = δj ′ and ID(Sj ) < ID(Sj ′ ).
Consider any subset T ⊆ S. Let U = U1 ∪ U2 be a size-t subset U ⊆ T . We calculate the
probability that all vertices in U1 fail to select a color, and all vertices in U2 are decolored. Notice
that there are at most 2t ways of partitioning U into U1 ∪ U2 .
(j)
(j)
Suppose that U1 has size x. We write U1 = U1 ∩ Sj . Whether a vertex v ∈ U1 fails to select a
color only depends the random bits in Sj . Thus, by by Lemma 21, the probability that all vertices
(j)
Q
in U1 fail to select a color is at most kj=1 (O(δj ))|U1 | ≤ (O(δ))|U1 | . Recall δ = maxj:Sj ∩T 6=∅ δj .
(j)

(j)

Similarly, suppose that U2 has size y. We write U2 = U2 ∩ Sj . Whether a vertex v ∈ U2 is
decolored only depends the random bits in S1 , . . . , Sj . However, regardless of the random bits in
(j)

(j)

S1 , . . . , Sj−1 , the probability that all vertices in U2 are decolored is (O(δj ))|U1 | by Lemma 20.
log(|Sj |/Dj )
. Thus, the probability that all vertices in U2 are decolored is at most
Recall δ ≥ δj ≥
|Sj |
(j)
Qk
|U2 |
≤ (O(δ))|U2 | .
j=1 (O(δj ))

Therefore, by a union bound over (i) at most |Tt | choices of a size-t subset U ⊆ T , and (ii) at
most 2t ways of partitioning U into U1 ∪ U2 , the probability
that the number of uncolored vertices

in T is at least t is at most 2t · |Tt | · (O(δ))t = |Tt | · (O(δ))t .

27

