$\operatorname*{\textnormal{Pr}}\left(\text{there is a witness pair $(S,T)$
with $\left|{S}\right|\leqslant
2\Delta/3$}\right)\leqslant\sum_{s=1}^{2\Delta/3}{{\left|{\mathcal{L}}\right|}\choose{s}}\cdot
n^{-7\left|{s}\right|}<n^{-5}.$

###### Case 2: when $\left|{S}\right|>2\Delta/3$.

Again, fix any choice of the set $T$ with
$\left|{T}\right|=\left|{S}\right|-1$ from $\mathcal{R}$. This time, by Claim
13, degree of every color-node _not_ in $T$ is at least $3\Delta/4$ in
$\mathcal{G}_{\textnormal{{Base}}}$. This means that neighborhood of each such
color-node intersects with $S$ in at least
$3\Delta/4-(\Delta-2\Delta/3)=5\Delta/12$ (as
$\left|{\mathcal{L}}\right|\leqslant\Delta$) vertex-nodes. In other words,
there are at least $\left|{\mathcal{R}\setminus T}\right|\cdot 5\Delta/12$
edges between $S$ and $\mathcal{R}\setminus T$ in
$\mathcal{G}_{\textnormal{{Base}}}$. Thus,

$\operatorname*{\textnormal{Pr}}\left(\text{$(S,T)$ is a witness
pair}\right)\leqslant\left(1-\frac{\beta}{\Delta}\right)^{\left|{\mathcal{R}\setminus
T}\right|\cdot
5\Delta/12}\leqslant\exp\left(-\frac{500}{12}\cdot\left|{\mathcal{R}\setminus
T}\right|\cdot\log{n}\right)<n^{-40\left|{\mathcal{R}\setminus T}\right|},$

by the choice of $\beta$ in Eq. 1. A union bound over all
${{\left|{\mathcal{R}}\right|}\choose{\left|{T}\right|}}={{\left|{\mathcal{R}}\right|}\choose{\left|{\mathcal{R}\setminus
T}\right|}}<n^{\left|{\mathcal{R}\setminus T}\right|}$ choices for $T$ then
implies that for any such $S$,

$\operatorname*{\textnormal{Pr}}\left(\text{there is a set $T$ so that $(S,T)$
is a witness pair}\right)\leqslant n^{\left|{\mathcal{R}\setminus
T}\right|}\cdot n^{-40\left|{\mathcal{R}\setminus T}\right|}\leqslant
n^{-39\cdot(\left|{\mathcal{R}}\right|-\left|{S}\right|+1)},$

where we used the fact that $\left|{T}\right|=\left|{S}\right|-1$. Now note
that the number of choices for the set $S$ of a fixed size is

${{\left|{\mathcal{L}}\right|}\choose{\left|{S}\right|}}={{\left|{\mathcal{L}}\right|}\choose{\left|{\mathcal{L}}\right|-\left|{S}\right|}}\leqslant
n^{\left|{\mathcal{L}}\right|-\left|{S}\right|}\leqslant
n^{\left|{\mathcal{R}}\right|-\left|{S}\right|},$

where the last inequality uses the fact that
$\left|{\mathcal{R}}\right|\geqslant\left|{\mathcal{L}}\right|$. As a result,

$\operatorname*{\textnormal{Pr}}\left(\text{there is a witness pair $(S,T)$
with
$\left|{S}\right|>2\Delta/3$}\right)\leqslant\sum_{s=2\Delta/3}^{\left|{\mathcal{L}}\right|}n^{\left|{\mathcal{R}}\right|-\left|{S}\right|}\cdot
n^{-39\cdot(\left|{\mathcal{R}}\right|-\left|{S}\right|+1)}<n^{-39}.$

Finally, by combining Case 1 and 2 above, we have that with high probability,
there is no witness set $(S,T)$ in $\mathcal{G}_{\textnormal{{Sample}}}$. This
implies that for every $A\subseteq\mathcal{L}$, we have
$\left|{N_{\mathcal{G}_{\textnormal{{Sample}}}}(A)}\right|\geqslant\left|{A}\right|$,
which, by Hall’s theorem (Fact 1), implies that
$\mathcal{G}_{\textnormal{{Sample}}}$ has an $\mathcal{L}$-perfect matching.

Lemma 5.3 now follows immediately from Claims 12, 13 and 15 as described
earlier.

######  Remark 5.6.

Before moving on from this subsection, let us mention why our coloring
procedure attempts to color lonely small almost-cliques (Phase 2) before the
remaining sparse vertices. In Claim 13, we crucially used the fact that we can
use the lists used to color $C$ so far as a proxy for approximating the event
$C(v)=c$ with $c\in L_{1}(v)\cup L_{2}(v)$, instead. This was okay because
these lists are of relatively small size to make the argument go through.
However, coloring sparse vertices requires us to use the lists $L_{3}(\cdot)$
which are much larger and thus would break this claim entirely.

Concretely, in Claim 13, we had $O(\varepsilon\Delta^{2})$ edges going out of
the almost-clique and each was responsible for blocking a fixed color on a
vertex with probability $p=O(\beta/\Delta)$ which is governed by sizes of
$L_{1}(\cdot),L_{2}(\cdot)$. This meant that each color was blocked for
$O(\varepsilon\cdot\beta\cdot\Delta)$ vertices which can be made $o(\Delta)$
by taking $\varepsilon$ sufficiently smaller than $\beta$. Nevertheless, had
we also included lists $L_{3}(\cdot)$, then the right probability parameter
$p$ would have become $O(\beta/(\varepsilon^{2}\Delta))$ which is crucial for
coloring $\varepsilon$-sparse vertices; but then, it meant that the bound we
got on the number of blocked vertices for a color is actually
$O(\varepsilon\Delta^{2}\cdot\beta/(\varepsilon^{2}\Delta))=O(\Delta/\varepsilon)$
which is $>\Delta$ no matter the tuning of parameters.

####  5.3 Phase 3: Sparse Vertices

In this phase, we will describe an algorithm to extend the partial coloring
$C_{2}$ to all vertices of $V_{\textnormal{sparse}}$. The key observation is
that for any extension of $C_{1}$ (i.e. $C_{2}$, and every intermediate
coloring in this phase), the gap between available colors and remaining degree
created by $C_{1}$ for each sparse vertex (see Lemma 5.2) does not shrink.
This is because if $C$ is an extension of $C_{1}$, each additional neighbor of
some sparse vertex $v$ that $C$ colors, increases $\mathsf{coldeg}_{C}(v)$ by
$1$, and decreases $\mathsf{avail}_{C}(v)$ by at most $1$, keeping the gap
intact. We have the following lemma for this phase:

######  Lemma 5.7.

With high probability, there exists a proper partial $\Delta$-coloring $C$
that is an extension of $C_{2}$ and colors all remaining vertices in
$V_{\textnormal{sparse}}$ using only the colors in the lists $L_{3}(v)$ for
sparse vertices $v\in V_{\textnormal{sparse}}$ (and thus the randomness is
also only over these lists).

Once again, since the lemma is not new, its proof is postponed to Section B.2.

We note that $C$ is _not_ the final coloring we obtain in this phase. Instead,
we are going to update $C$ to a proper $\Delta$-coloring $C_{3}$ that colors
all vertices in $V_{\textnormal{sparse}}$ as well as all small almost-cliques
in $\mathcal{K}_{\textnormal{lonely}}$ handled by Phase 2; however, we shall
remove the color of every other vertex $v$, i.e., set $C_{3}(v)=\perp$ for
them. Such vertices are solely colored by the one-shot-coloring algorithm and
we no longer need their guarantees as we are done coloring sparse vertices.
Thus, to summarize:

  * •

$C_{3}$ is a proper partial $\Delta$-coloring of all vertices in
$V_{\textnormal{sparse}}$ as well as small almost-cliques in
$\mathcal{K}_{\textnormal{lonely}}$ and does not color any other vertex (we
also require no further properties from $C_{3}$ and it might as well be
considered adversarially chosen from now on).

####  5.4 Phase 4: Holey Almost-Cliques

In this phase, we will extend the partial coloring $C_{3}$ to all vertices in
holey almost-cliques.

######  Lemma 5.8.

There exists a proper partial $\Delta$-coloring $C_{4}$ that is an extension
of $C_{3}$ and assigns a color to every vertex $v$ in each holey almost-clique
using a color from $L_{4}(v)$. The randomness in this lemma is only over the
lists $L_{4}(\cdot)$ of all vertices.

As discussed in the overview of the coloring algorithm, we will iterate over
all almost-cliques in our decomposition, and attempt to color them assuming
that they are holey. The main tool to show that this succeeds on holey almost-
cliques is the following lemma, which shows that any coloring outside a holey
almost-clique can be extended to it while using only the lists $L_{4}(\cdot)$
on vertices inside it.

######  Lemma 5.9.

For a holey almost-clique $K$, and any partial $\Delta$-coloring $C$ outside
$K$, there exists, with high probability, a coloring $C^{\prime}$ which
extends $C$ to $K$ such that $C^{\prime}(v)\in L_{4}(v)$ for all $v\in K$.

The proof is almost verbatim from [7], except that we have to go through every
step carefully to make sure it works for $\Delta$-coloring—hence we provide it
in Section B.3 for completeness.

Lemma 5.8 now follows immediately from Lemma 5.9 by going over all uncolored
almost-cliques at this point one by one, and apply this lemma with $C$ being
the current coloring, and $C^{\prime}$ being the one we can update this
coloring to. Thus, at the end, we obtain the desired $C_{4}$.

####  5.5 Phase 5: Unholey Critical Almost-Cliques

In this phase, we will color unholey critical almost-cliques. In particular,
we have a set $\mathcal{K}_{\textnormal{critical}}$ of almost-cliques, and for
each $K\in\mathcal{K}_{\textnormal{critical}}$, a critical-helper structure
$(u,v,N(v))$ (Definition 4.6). The main lemma of this section is:

######  Lemma 5.10.

With high probability, there exists a proper partial $\Delta$-coloring $C_{5}$
that is an extension of $C_{4}$ and satisfies the following properties: $(i)$
it colors vertices of all almost-cliques in
$\mathcal{K}_{\textnormal{critical}}$; and $(ii)$ for any vertex $v$, if
$C_{5}(v)\notin L(v)$, then $N_{H^{+}}(v)=N_{G}(v)$; that is, we can only
color $v$ with a color not from $L(v)$ if we know its entire neighborhood (via
the critical helper structure).

The randomness in this lemma is only over the lists $L_{5}(v)$ for vertices
$v$ in $\mathcal{K}_{\textnormal{critical}}$.

This is the first phase in which we use our out-of-palette-coloring idea – we
do not require that $C_{5}(v)\in L(v)$ always holds in this lemma. In
particular, for the vertex $v$ in the critical-helper $(u,v,N(v))$, we are
going to use a color out of its sampled palette. Since we know the entire
neighborhood of $v$, we at least have enough information to avoid an improper
coloring.

The proof of the lemma is algorithmic. We start with a brief overview. The
plan (as always) is to iterate over the almost-cliques of
$\mathcal{K}_{\textnormal{critical}}$ in arbitrary order, and extend the
coloring $C_{4}$ to eventually color all of them. For a particular almost-
clique $K\in\mathcal{K}_{\textnormal{critical}}$, we will use the critical-
helper structure $(u,v,N(v))$ to assign the _same_ color to both $u$ and $v$.
The reason we can do this is that we know all the neighbors of $v$, and hence
can pick a color in the list $L_{5}(u)$ that can be assigned to both of them –
existence of such a color in the first place is because both $u$ and $v$
belong to an almost-clique and thus have at most $O(\varepsilon\Delta)$ edges
to outside; thus, as long as we have sampled a color out of these many, which
will happen with high probability, we can find such a color. Having done that,
the rest of $K$ can be colored by palette sparsification: the imbalance we
create by giving two vertices the same color is just enough for it to succeed
with high probability.

Input: critical almost-cliques $\mathcal{K}_{\textnormal{critical}}$, a
critical-helper structure

for each $K\in\mathcal{K}_{\textnormal{critical}}$, and the partial coloring
$C_{4}$.

  1. $(i)$

Initialize $C\leftarrow C_{4}$. For each $K\in\mathcal{K}$:

     * •

Let $(u,v,N(v))$ be the critical-helper structure for $K$ of Part
($\emph{6}.$) of Section 4.5.

     * •

Find a color $c\in L_{5}(u)$ that is not used in $N_{H^{+}}(u)\cup
N_{H^{+}}(v)$ by $C$, and set

$C(u)\leftarrow c\quad\text{and}\quad C(v)\leftarrow c.$

     * •

Extend $C$ to color $K\setminus\\{u,v\\}$ with the color of each vertex $w$
chosen from $L_{5}(w)$, by constructing the sampled palette graph of $K$ with
respect to $C$ and sampled lists $\SS:=\left\\{L_{5}(w)\mid w\in K\right\\}$
exactly as in Algorithm 5 (see Claim 18 for details).

  2. $(ii)$

Return $C_{5}\leftarrow C$ as the output coloring.

Algorithm 6 The unholey-critical-coloring algorithm.

This algorithm claims to color all of the almost-cliques in
$\mathcal{K}_{\textnormal{critical}}$, but it is not obvious at all that each
of its steps is possible. We will prove this in the following series of
claims.

######  Claim 16.

With high probability, there exists a color $c\in L_{5}(u)$ such that $c$ is
not used by $C$ in $N_{G}(u)\cup N_{G}(v)$. Further, there is an algorithm
that can find this color if it exists.

######  Proof 5.11.

Recall that $u$ and $v$ have at most $10\varepsilon\Delta$ neighbors each
outside $K$, and hence only at most $20\varepsilon\Delta$ neighbors in total
which are colored by $C$ (see 5.11). [h!]

$u$$v$$K$$\leqslant 10\varepsilon\Delta$ coloredneighbors$\leqslant
10\varepsilon\Delta$ coloredneighbors

$L_{5}(u)$ has a color not used by $C$ over $N(u)\cup N(v)$.

Let $\mathsf{Avail}_{C}(u,v)$ be the set of colors in $\left[\Delta\right]$
that are not used in the neighborhood of $u$ or $v$ by the coloring $C$. Then

$\left|{\mathsf{Avail}_{C}(u,v)}\right|\geqslant\Delta-20\varepsilon\Delta\geqslant\Delta/2.$

We would like to show that is small. Since each color from
$\mathsf{Avail}_{C}(u,v)$ is sampled into $L_{5}(u)$ independently with
probability $\beta/\Delta$, the probability that none of them are in
$L_{5}(u)$ is at most:

$\left(1-\frac{\beta}{\Delta}\right)^{\Delta/2}\leqslant\exp\left(-\frac{\beta\cdot\Delta}{2\Delta}\right)=n^{-50}.$

Hence a “good” color exists with high probability.

To find this color, we note that the critical-helper structure contains $N(v)$
and while we do not necessarily know all the neighbors of $u$ in $G$, we do
know the ones that:

  * •

Have a color from $L_{5}(u)$ in their own palette.

  * •

Were assigned a color _outside_ their palette – since for such vertices we
know all of their neighbors by the invariant maintained in Lemma 5.10.

This means that we can iterate over the colors in $[{\Delta}]$, and check for
each one whether it is used by $N_{H^{+}}(u)\cup N_{H^{+}}(v)$, which serves
as a proxy for checking $N_{G}(u)\cup N_{G}(v)$, and we are done.

We now have to perform a somewhat daunting task—to extend the coloring $C$ to
the rest of the almost-clique $K$. It turns out that the small imbalance we
create in the previous line (by coloring $2$ vertices with $1$ color) is
enough for palette sparsification to come to our rescue.

######  Claim 18.

With high probability, $K\setminus\\{u,v\\}$ can be colored as an extension of
$C$, while coloring each vertex $w\in K\setminus\\{u,v\\}$ with a color from
$L_{5}(w)$.

######  Proof 5.12.

Consider the base and the sampled palette graphs
$\mathcal{G}_{\textnormal{{Base}}}$ and $\mathcal{G}_{\textnormal{{Sample}}}$
(Definitions 3.8 and 3.9) corresponding to the partial coloring $C$, with:

  * •

$\mathcal{L}:=K\setminus\\{u,w\\}$,

  * •

$\mathcal{R}:=\left[\Delta\right]\setminus\\{c\\}$, where $c$ is the color
assigned to $u$ and $v$, and

  * •

$S(v):=L_{5}(v)$ for all $v\in\mathcal{L}$.

Recall that an $\mathcal{L}$-perfect matching in
$\mathcal{G}_{\textnormal{{Sample}}}$ implies a coloring of remaining vertices
in $K$ from their $L_{5}(\cdot)$ lists which is further an extension of $C$.
We are going to use Lemma 3.10 to obtain that
$\mathcal{G}_{\textnormal{{Sample}}}$ has a perfect matching.

For this, we need to establish the required properties of
$\mathcal{G}_{\textnormal{{Base}}}$. Proceeding in the same order as the lemma
(recall that $m$ denotes $\left|{\mathcal{L}}\right|$ in this lemma):

  1. $(i)$

$m\leqslant\left|{\mathcal{R}}\right|\leqslant 2m$: In this instance,
$\left|{L}\right|=\left|{R}\right|$, so both inequalities follow trivially.

  2. $(ii)$

The minimum degree of any vertex in $\mathcal{L}$ is at least $2m/3$: Note
that any vertex $v\in\mathcal{L}$ is in $K$, and hence has only at most
$10\varepsilon\Delta$ edges going out of $K$ (in $G$, the input graph). Hence
there are at most $10\varepsilon\Delta$ colors that are blocked for $v$, and
$\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{\mathcal{R}}\right|-10\varepsilon\Delta\geqslant(2/3)\cdot
m$.

  3. $(iii)$

For any subset $A\subseteq\mathcal{L}$ such that $\left|{A}\right|\geqslant
m/2$,

$\sum_{v\in
A}\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{A}\right|\cdot
m-m/4.$

Let $t$ denote the number of non-edges in $K$, and recall that since $K$ is
unholey, $t\leqslant 10^{7}\cdot\varepsilon\Delta<\Delta/10$. Note that any
vertex $v\in K$ has at most
$\Delta-(\left|{K}\right|-1-\overline{\deg}_{K}({v}))$ neighbors (in $G$)
outside $K$, because $\deg_{G}(v)\leqslant\Delta$, and $v$ has exactly
$\left|{K}\right|-1-\overline{\deg}_{K}({v})$ neighbors inside $K$. But since
each non-edge between $v\in\mathcal{L}$ and a color in $\mathcal{R}$
corresponds to an edge from $v$ to outside $K$, we have:

$\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{R}\right|-(\Delta+1)+\left|{K}\right|-\overline{\deg}_{K}({v}).$

By summing this inequality for all $v\in A$, we get:

$\displaystyle\sum_{v\in A}\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)$
$\displaystyle\geqslant\sum_{v\in
A}\left|{R}\right|-(\Delta+1)+\left|{K}\right|-\overline{\deg}_{K}({v})$
$\displaystyle=\sum_{v\in
A}\underbrace{\Delta-1}_{\left|{R}\right|}-(\Delta+1)+\underbrace{\left|{\mathcal{L}}\right|+2}_{\left|{K}\right|}-\overline{\deg}_{K}({v})$
$\displaystyle=\sum_{v\in
A}\left|{\mathcal{L}}\right|-\overline{\deg}_{K}({v})=\left|{A}\right|\cdot
m-\underbrace{\sum_{v\in A}\overline{\deg}_{K}({v})}_{\leqslant 2t}$
$\displaystyle\geqslant\left|{A}\right|\cdot m-m/4.$

Each edge of $\mathcal{G}_{\textnormal{{Base}}}$ is sampled into
$\mathcal{G}_{\textnormal{{Sample}}}$ independently with probability

$\beta/\Delta\geqslant 99\log n/m\geqslant 20/m\cdot(\log n+3\cdot\log n).$

By Lemma 3.10 $\mathcal{G}_{\textnormal{{Sample}}}$ has a perfect matching
with probability at least $(1-n^{-3})$.

This concludes the proof of Lemma 5.10.

####  5.6 Phase 6: Unholey Friendly (or Social) Small Almost-Cliques

In this (final!) phase, we describe an algorithm that takes the partial
coloring $C_{5}$ and from it compute a proper $\Delta$-coloring of the entire
graph by coloring the remaining vertices. This step however is the one that
includes our _recoloring_ ideas and thus the coloring we obtain is no longer
an extension of $C_{5}$.

We are left with a set $\mathcal{K}_{\textnormal{friendly}}$ of unholey small
almost-cliques, that may be friendly or social. For each
$K\in\mathcal{K}_{\textnormal{friendly}}$, we have a friendly-helper
$(u,v,w,N(v),N(w))$ (Definition 4.7). Note in particular that we will actually
edit the color assigned to some vertices, so the coloring obtained by this
algorithm is not necessarily an extension of $C_{5}$. We show the following
lemma:

######  Lemma 5.13.

Given the coloring $C_{5}$ from the previous section, with high probability
there exists a proper coloring $C_{6}$ that colors the entire graph such that:
For any vertex $v$, if $C_{6}(v)\notin L(v)$, $N_{G}(v)=N_{H^{+}}(v)$. That
is, we can color $v$ with a color not from $L(v)$ only if we know its entire
neighborhood (via the friendly-helper structure).

The randomness in this lemma is over the lists $L_{6,i}(v)$ for all vertices
$v\in V$ and all $i\in[2\beta]$ (even including vertices that were colored
before this phase).

Once again, we will prove the lemma with an algorithm. The idea is the same,
to extend the coloring $C_{5}$ to each almost-clique in
$\mathcal{K}_{\textnormal{friendly}}$ one-by-one, with a key difference being
that we will go back and edit the color of one vertex per almost-clique we
color.

For an almost-clique $K$, we will use its friendly-helper structure
$(u,v,w,N(v),N(w))$ to assign the same color to $u$ and $w$, and then invoke
palette sparsification to color the rest of $K$.

Input: The set of almost-cliques $\mathcal{K}_{\textnormal{friendly}}$, a
friendly-helper structure for each $K\in\mathcal{K}_{\textnormal{friendly}}$,
and the partial coloring $C_{5}$.

  1. $(i)$

Initialize $C=C_{5}$, and an index $i_{u}\leftarrow 0$ for each vertex $u\in
V(G)$ (this keeps track of how many times we recolored $u$).

  2. $(ii)$

For each $K\in\mathcal{K}_{\textnormal{friendly}}$:

     * •

Let $(u,v,w,N(v),N(w))$ be the friendly-helper structure of $K$.

     * •

Find a color $c\in L_{6,i_{u}}(u)$ such that $c\notin C(N_{H^{+}}(u)\cup
N_{H^{+}}(w))$ and set

$C(u)\leftarrow c\quad\text{and}\quad C(w)\leftarrow c.$

Update $i_{u}\leftarrow i_{u}+1$ (we emphasize that $u$ is not part of $K$ but
rather a neighbor to it).

     * •

Extend $C$ to color $K\setminus\\{v,w\\}$ with each remaining vertex $x$
getting a color from $L_{6,2\beta}(x)$ exactly as in Algorithm 6 (see Claim 21
for details).

     * •

Extend $C$ to color $v$ by finding a color that does not appear in
$N_{H+}(v)$.

  3. $(iii)$

Return $C_{6}\leftarrow C$ as the output.

Algorithm 7 The unholey-friendly-coloring algorithm.

As before, while the algorithm claims to color all the almost-cliques in
$\mathcal{K}_{\textnormal{friendly}}$, it is far from obvious that each step
it performs is possible. We show that this is indeed the case.

######  Claim 19.

With high probability, there exists a color in $L_{6,i_{u}}(u)$ that does not
appear in $C$ over $N(u)\cup N(w)$. Further, there is an algorithm that can
find this color if it exists.

######  Proof 5.14.

The crucial observation is that since $u$ is not a stranger to $K$, it has at
least $\Delta/\beta$ uncolored neighbors in the coloring $C$. Further, since
$w\in K$ – an almost-clique – it has at most $10\varepsilon\Delta$ neighbors
outside $K$, and hence only at most $10\varepsilon\Delta$ neighbors that
receive colors in $C$. Hence there are at least
$\Delta/\beta-10\varepsilon\Delta\geqslant\Delta/2\beta$ colors that are not
used by $C$ in $N(u)\cup N(w)$ (see 5.14).

[h!]

$w$$u$$K$$\leqslant 10\varepsilon\Delta$
coloredneighbors$\geqslant\frac{\Delta}{\beta}$ uncoloredneighbors

$L_{6,i_{u}}(u)$ has a color not used by $C$ over $N(u)\cup N(w)$.

Let $\mathsf{Avail}_{C}(u,w)$ denote this set of colors. We are interested in
showing that the probability is small. We start with the technical note that
this is the first time (any part of) the coloring algorithm is looking at
$L_{6,i_{u}}(u)$, and hence this particular list is independent of $C$
entirely. Recall that each color from $\mathsf{Avail}_{C}(u,w)$ is in
$L_{6,i_{u}}(u)$ independently with probability $\beta^{2}/\Delta$. Hence the
probability that none of them is in $L_{6,i_{u}}(u)$ is at most:

$\left(1-\frac{\beta^{2}}{\Delta}\right)^{\Delta/2\beta}\leqslant\exp\left(-\frac{\beta^{2}\cdot\Delta}{2\beta\cdot\Delta}\right)=n^{-50}.$

So there is a color $c$ that satisfies our requirements with high probability.
To find $c$ we can iterate over the colors of $L_{6,i_{u}}(u)$ and check
whether $c$ is used by $C$ in $N_{H^{+}}(u)\cup N_{H^{+}}(w)$. As before, this
is a proxy for checking that $c$ is used in $N_{G}(u)\cup N_{G}(w)$, and it
works because $c\in L(u)$, $N_{H^{+}}(w)=N_{G}(w)$, and if any neighbor of $u$
picked a color out of its palette, it will be in $N_{H^{+}}(u)$.

Note that we increment $i_{v}$ in the final line to get a “fresh” list for the
next time we have to color $v$—this happens at most $\beta$ times for a vertex
$v$ (since it must be a non-stranger to some almost clique $K$ to be
recolored), and $L_{6}$ has $2\beta$ lists for each $v$, so there are always
enough lists to go around.

Next, we have the palette sparsification analogue of this phase.

######  Claim 21.

With high probability, $K\setminus\\{v,w\\}$ can be colored as an extension of
$C$, where the color of each vertex $x\in K\setminus\\{v,w\\}$ is from
$L_{6,2\beta}(x)$.

######  Proof 5.15.

Consider the base and the sampled palette graphs
$\mathcal{G}_{\textnormal{{Base}}}$ and $\mathcal{G}_{\textnormal{{Sample}}}$
(Definitions 3.8 and 3.9) corresponding to the partial coloring $C$, with:

  * •

$\mathcal{L}=K\setminus\\{v,w\\}$,

  * •

$\mathcal{R}=\left[\Delta\right]\setminus\\{c\\}$, where $c$ is the color
assigned to $u$ and $w$, and

  * •

$S(x)=L_{6,2\beta}(x)$ for all $x\in\mathcal{L}$.

Recall that an $\mathcal{L}$-perfect matching in
$\mathcal{G}_{\textnormal{{Sample}}}$ gives a coloring which extends $C$ to
$\mathcal{L}$ using only colors from the list $L_{6,2\beta}$. Hence our focus
shifts to showing that $\mathcal{G}_{\textnormal{{Base}}}$ has the properties
required by Lemma 3.10 to obtain that $\mathcal{G}_{\textnormal{{Sample}}}$
has a perfect matching. Proceeding in the same order as the lemma:

  1. $(i)$

$m\leqslant\left|{\mathcal{R}}\right|\leqslant 2m$: The first inequality
follows from the fact that $\left|{\mathcal{R}}\right|=\Delta-1$, and
$m\leqslant\Delta-2$ (since $K$ is a _small_ almost-clique, and we removed two
vertices from it). For the second one, note that
$2m=2\left|{K}\right|-4\geqslant 3/2\cdot\Delta$.

  2. $(ii)$

The minimum degree of any vertex in $\mathcal{L}$ is at least $2m/3$. Note
that any vertex $v\in\mathcal{L}$ is in $K$, and hence has only at most
$10\varepsilon\Delta$ edges going out of $K$ (in $G$, the input graph). Hence
there are at most $10\varepsilon\Delta$ colors that are blocked for $v$, and
$\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{\mathcal{R}}\right|-10\varepsilon\Delta\geqslant
2m/3$ (the last inequality is from combining parts (i) and (ii) above).

  3. $(iii)$

For any subset $S\subset\mathcal{L}$ such that $\left|{S}\right|\geqslant
m/2$,

$\sum_{v\in
S}\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left(\left|{S}\right|\cdot
m\right)-m/4.$

Since the only facts we use are that $K$ is unholey, and points $(i)$ and
$(ii)$ above, the proof is exactly the same as in Claim 18.

And once again, by invoking Lemma 3.10 we are done.

To finish up, note that $v$ has two neighbors ($u$ and $w$) with the same
color, and we know its entire neighborhood. Hence we can find a color to
assign to it, and we are done.

This concludes the proof of Lemma 5.13. As at this point, all vertices of the
graph are colored, we obtain a proper $\Delta$-coloring of $G$. This in turn
concludes the proof of Theorem 1.1.

#### Acknowledgements

Sepehr Assadi would like to thank Soheil Behnezhad, Amit Chakrabarti, Prantar
Ghosh, and Merav Parter for helpful conversations. We thank the organizers of
DIMACS REU in Summer 2020, in particular Lazaros Gallos, for initiating this
collaboration and all their help and encouragements along the way. We are also
thankful to the anonymous reviewers of STOC 2022 and TheoretiCS for helpful
comments and suggestions on the presentation of the paper.

### References

  * [1] “Lecture Notes on Palette Sparsification for $(\Delta+1)$ Coloring by Sepehr Assadi” Accessed: 2023-05-08, https://sepehr.assadi.info/courses/cs671-f20/lec3.pdf, 2020
  * [2] Amir Abboud, Keren Censor-Hillel, Seri Khoury and Ami Paz  “Smaller Cuts, Higher Lower Bounds”  In _ACM Trans. Algorithms_ 17.4, 2021, pp. 30:1–30:40  DOI: 10.1145/3469834
  * [3] Kook Jin Ahn, Sudipto Guha and Andrew McGregor  “Analyzing graph structure via linear measurements”  In _Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012_ SIAM, 2012, pp. 459–467  DOI: 10.1137/1.9781611973099.40
  * [4] Noga Alon and Sepehr Assadi  “Palette Sparsification Beyond ($\Delta$+1) Vertex Coloring”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference_ 176, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 6:1–6:22  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.6
  * [5] Noga Alon and Michael Tarsi  “Colorings and orientations of graphs”  In _Comb._ 12.2, 1992, pp. 125–134  DOI: 10.1007/BF01204715
  * [6] Sepehr Assadi, Andrew Chen and Glenn Sun  “Deterministic graph coloring in the streaming model”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 261–274  DOI: 10.1145/3519935.3520016
  * [7] Sepehr Assadi, Yu Chen and Sanjeev Khanna  “Sublinear Algorithms for ($\Delta$ \+ 1) Vertex Coloring”  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019_ SIAM, 2019, pp. 767–786  DOI: 10.1137/1.9781611975482.48
  * [8] Sepehr Assadi, Pankaj Kumar and Parth Mittal  “Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for $\Delta$-coloring”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 234–247  DOI: 10.1145/3519935.3520005
  * [9] Sepehr Assadi and Chen Wang  “Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions”  In _13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA_ 215, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 10:1–10:20  DOI: 10.4230/LIPIcs.ITCS.2022.10
  * [10] Bradley Baetz and David R. Wood  “Brooks’ Vertex-Colouring Theorem in Linear Time”  In _CoRR_ abs/1401.8023, 2014  arXiv: http://arxiv.org/abs/1401.8023
  * [11] Alkida Balliu, Sebastian Brandt, Fabian Kuhn and Dennis Olivetti  “Distributed $\Delta$-coloring plays hide-and-seek”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 464–477  DOI: 10.1145/3519935.3520027
  * [12] Paul Beame, Paraschos Koutris and Dan Suciu  “Communication Steps for Parallel Query Processing”  In _J. ACM_ 64.6, 2017, pp. 40:1–40:58  DOI: 10.1145/3125644
  * [13] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel and Hamed Saleh  “Streaming and Massively Parallel Algorithms for Edge Coloring”  In _27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany_ 144, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 15:1–15:14  DOI: 10.4230/LIPIcs.ESA.2019.15
  * [14] Suman K. Bera, Amit Chakrabarti and Prantar Ghosh  “Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models”  In _47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)_ 168, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 11:1–11:21  DOI: 10.4230/LIPIcs.ICALP.2020.11
  * [15] Suman Kalyan Bera and Prantar Ghosh  “Coloring in Graph Streams”  In _CoRR_ abs/1807.07640, 2018  arXiv: http://arxiv.org/abs/1807.07640
  * [16] Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra and Anannya Upasana  “Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!”  In _12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference_ 185, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 15:1–15:19  DOI: 10.4230/LIPIcs.ITCS.2021.15
  * [17] Oleg V. Borodin and Alexandr V. Kostochka  “On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density”  In _J. Comb. Theory, Ser. B_ 23.2-3, 1977, pp. 247–250  DOI: 10.1016/0095-8956(77)90037-5
  * [18] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela and Jara Uitto  “A lower bound for the distributed Lovász local lemma”  In _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ ACM, 2016, pp. 479–488  DOI: 10.1145/2897518.2897570
  * [19] Rowland Leonard Brooks  “On colouring the nodes of a network”  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 37.2, 1941, pp. 194–197  Cambridge University Press
  * [20] Harry Buhrman and Ronald Wolf  “Complexity measures and decision tree complexity: a survey”  In _Theor. Comput. Sci._ 288.1, 2002, pp. 21–43  DOI: 10.1016/S0304-3975(01)00144-X
  * [21] Mark Bun and Justin Thaler  “Dual lower bounds for approximate degree and Markov-Bernstein inequalities”  In _Inf. Comput._ 243, 2015, pp. 2–25  DOI: 10.1016/j.ic.2014.12.003
  * [22] Amit Chakrabarti, Prantar Ghosh and Manuel Stoeckl  “Adversarially Robust Coloring for Graph Streams”  In _13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA_ 215, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 37:1–37:23  DOI: 10.4230/LIPIcs.ITCS.2022.37
  * [23] Yi-Jun Chang, Wenzheng Li and Seth Pettie  “An optimal distributed $(\Delta+1)$-coloring algorithm?”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018_ ACM, 2018, pp. 445–456  DOI: 10.1145/3188745.3188964
  * [24] Graham Cormode, Jacques Dark and Christian Konrad  “Independent Sets in Vertex-Arrival Streams”  In _46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece_ 132, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 45:1–45:14  DOI: 10.4230/LIPIcs.ICALP.2019.45
  * [25] Daniel W. Cranston and Landon Rabern  “Brooks’ Theorem and Beyond”  In _J. Graph Theory_ 80.3, 2015, pp. 199–225  DOI: 10.1002/jgt.21847
  * [26] Artur Czumaj, Peter Davies and Merav Parter  “Improved Deterministic $(\Delta+1)$ Coloring in Low-Space MPC”  In _PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021_ ACM, 2021, pp. 469–479  DOI: 10.1145/3465084.3467937
  * [27] Artur Czumaj, Peter Davies and Merav Parter  “Simple, Deterministic, Constant-Round Coloring in the Congested Clique”  In _PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020_ ACM, 2020, pp. 309–318  DOI: 10.1145/3382734.3405751
  * [28] Abhik Kumar Das and Sriram Vishwanath  “On finite alphabet compressive sensing”  In _IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2013, Vancouver, BC, Canada, May 26-31, 2013_ IEEE, 2013, pp. 5890–5894  DOI: 10.1109/ICASSP.2013.6638794
  * [29] Devdatt P. Dubhashi and Alessandro Panconesi  “Concentration of Measure for the Analysis of Randomized Algorithms”  Cambridge University Press, 2009  URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/
  * [30] Paul Erdős, Arthur L Rubin and Herbert Taylor  “Choosability in graphs”  In _Congr. Numer_ 26.4, 1979, pp. 125–157
  * [31] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri and Jian Zhang  “Graph Distances in the Data-Stream Model”  In _SIAM J. Comput._ 38.5, 2008, pp. 1709–1727  DOI: 10.1137/070683155
  * [32] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri and Jian Zhang  “On graph problems in a semi-streaming model”  In _Theor. Comput. Sci._ 348.2-3, 2005, pp. 207–216  DOI: 10.1016/j.tcs.2005.09.013
  * [33] Manuela Fischer, Magnús M. Halldórsson and Yannic Maus  “Fast Distributed Brooks’ Theorem”  In _Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023_ SIAM, 2023, pp. 2567–2588  DOI: 10.1137/1.9781611977554.ch98
  * [34] Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn and Yannic Maus  “Improved Distributed Delta-Coloring”  In _Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018_ ACM, 2018, pp. 427–436  URL: https://dl.acm.org/citation.cfm?id=3212764
  * [35] Péter Hajnal and Endre Szemerédi  “Brooks Coloring in Parallel”  In _SIAM J. Discret. Math._ 3.1, 1990, pp. 74–80  DOI: 10.1137/0403008
  * [36] Philip Hall  “On representatives of subsets”  In _Classic Papers in Combinatorics_ Springer, 1987, pp. 58–62
  * [37] Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja and Mario Szegedy  “Streaming Algorithms for Independent Sets in Sparse Hypergraphs”  In _Algorithmica_ 76.2, 2016, pp. 490–501  DOI: 10.1007/s00453-015-0051-5
  * [38] Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus and Tigran Tonoyan  “Efficient randomized distributed coloring in CONGEST”  In _STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021_ ACM, 2021, pp. 1180–1193  DOI: 10.1145/3406325.3451089
  * [39] Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin and Tigran Tonoyan  “Near-optimal distributed degree+1 coloring”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 450–463  DOI: 10.1145/3519935.3520023
  * [40] Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy and Chengu Wang  “Streaming and Communication Complexity of Clique Approximation”  In _Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I_ 7391, Lecture Notes in Computer Science  Springer, 2012, pp. 449–460  DOI: 10.1007/978-3-642-31594-7“˙38
  * [41] David G. Harris, Johannes Schneider and Hsin-Hao Su  “Distributed $(\Delta+1)$-coloring in sublogarithmic rounds”  In _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ ACM, 2016, pp. 465–478  DOI: 10.1145/2897518.2897533
  * [42] T.. Jayram, Ravi Kumar and D. Sivakumar  “Two applications of information complexity”  In _Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA_ ACM, 2003, pp. 673–682  DOI: 10.1145/780542.780640
  * [43] Mauricio Karchmer and Joseph Naor  “A Fast Parallel Algorithm to Color a Graph with Delta Colors”  In _J. Algorithms_ 9.1, 1988, pp. 83–91  DOI: 10.1016/0196-6774(88)90006-5
  * [44] Howard J. Karloff  “An NC Algorithm for Brooks’ Theorem”  In _Theor. Comput. Sci._ 68.1, 1989, pp. 89–103  DOI: 10.1016/0304-3975(89)90121-7
  * [45] Howard J. Karloff, Siddharth Suri and Sergei Vassilvitskii  “A Model of Computation for MapReduce”  In _Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010_ SIAM, 2010, pp. 938–948  DOI: 10.1137/1.9781611973075.76
  * [46] Alexandr V. Kostochka, Landon Rabern and Michael Stiebitz  “Graphs with chromatic number close to maximum degree”  In _Discret. Math._ 312.6, 2012, pp. 1273–1281  DOI: 10.1016/j.disc.2011.12.014
  * [47] László Lovász  “Three short proofs in graph theory”  In _Journal of Combinatorial Theory, Series B_ 19.3 Academic Press, 1975, pp. 269–271
  * [48] Andrew McGregor  “Graph stream algorithms: a survey”  In _SIGMOD Rec._ 43.1, 2014, pp. 9–20  DOI: 10.1145/2627692.2627694
  * [49] LS Melnikov and VG Vizing  “New proof of Brooks’ theorem”  In _Journal of Combinatorial Theory_ 7.4 Academic Press, 1969, pp. 289–290
  * [50] Michael Molloy and Bruce Reed  “Graph colouring and the probabilistic method”  Springer Science & Business Media, 2002
  * [51] Michael Molloy and Bruce A. Reed  “A Bound on the Strong Chromatic Index of a Graph”  In _J. Comb. Theory, Ser. B_ 69.2, 1997, pp. 103–109  DOI: 10.1006/jctb.1997.1724
  * [52] Michael Molloy and Bruce A. Reed  “Colouring graphs when the number of colours is almost the maximum degree”  In _J. Comb. Theory, Ser. B_ 109, 2014, pp. 134–195  DOI: 10.1016/j.jctb.2014.06.004
  * [53] Alessandro Panconesi and Aravind Srinivasan  “Improved Distributed Algorithms for Coloring and Network Decomposition Problems”  In _Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada_ ACM, 1992, pp. 581–592  DOI: 10.1145/129712.129769
  * [54] Alessandro Panconesi and Aravind Srinivasan  “The Local Nature of $\Delta$-Coloring and its Algorithmic Applications”  In _Comb._ 15.2, 1995, pp. 255–280  DOI: 10.1007/BF01200759
  * [55] Merav Parter  “$(Delta+1)$ Coloring in the Congested Clique Model”  In _45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic_ 107, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 160:1–160:14  DOI: 10.4230/LIPIcs.ICALP.2018.160
  * [56] Landon Rabern  “A different short proof of Brooks’ theorem”  In _Discussiones Mathematicae Graph Theory_ 34.3, 2014, pp. 633–634
  * [57] Landon Rabern  “Yet another proof of Brooks’ theorem”  In _Discrete Mathematics_ Elsevier, 2022, pp. 113261
  * [58] Jaikumar Radhakrishnan and Saswata Shannigrahi  “Streaming Algorithms for 2-Coloring Uniform Hypergraphs”  In _Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings_ 6844, Lecture Notes in Computer Science  Springer, 2011, pp. 667–678  DOI: 10.1007/978-3-642-22300-6“˙57
  * [59] Bruce A. Reed  “$\omega$, ${\Delta}$, and $\chi$”  In _J. Graph Theory_ 27.4, 1998, pp. 177–212  DOI: 10.1002/(SICI)1097-0118(199804)27:4“¡177::AID-JGT1“¿3.0.CO;2-K
  * [60] Bruce A. Reed  “A Strengthening of Brooks’ Theorem”  In _J. Comb. Theory, Ser. B_ 76.2, 1999, pp. 136–149  DOI: 10.1006/jctb.1998.1891
  * [61] Alexander A. Sherstov  “Approximating the AND-OR Tree”  In _Theory Comput._ 9, 2013, pp. 653–663  DOI: 10.4086/toc.2013.v009a020
  * [62] San Skulrattanakulchai  “Delta-List Vertex Coloring in Linear Time”  In _Algorithm Theory - SWAT 2002, 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings_ 2368, Lecture Notes in Computer Science  Springer, 2002, pp. 240–248  DOI: 10.1007/3-540-45471-3“˙25
  * [63] Michael Stiebitz and Bjarne Toft  “Brooks’s Theorem”  In _Topics in Chromatic Graph Theory_ Cambridge University Press, 2015, pp. 36–55
  * [64] Michel Talagrand  “Concentration of measure and isoperimetric inequalities in product spaces”  In _Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques_ 81 Springer, 1995, pp. 73–205

## Appendix

###  Appendix A Proofs of the Impossibility Results

We present the formal proofs of our impossibility results, alluded to Section
2.1, in this appendix. The first is in the query model, and shows that it is
essentially impossible to do better than the trivial algorithm that learns the
entire graph. The second is in the streaming setting, and shows that it is
essentially impossible to do better than to store the entire graph in a
slightly non-standard model where edges of the input can appear more than once
in the stream.

###### Notation:

We will use a boldface $\mathbf{x}$ to denote a vector (or a bit string), and
$x_{i}$ to index it.

####  A.1 Sublinear-Time Algorithms

In this section, we show that there is no algorithm in the general query model
that solves $\Delta$-coloring in $o(n\Delta)$ queries, via a reduction from
the $\textnormal{{and-or-one}}_{t,m}$ problem.

We assume that the vertices of the graph $G=(V,E)$ are _known_ , as is the
maximum degree $\Delta$. The general query model supports the following
queries on $G$:

  * •

Degree queries: Given a vertex $v\in V$, output $\deg(v)$.

  * •

Neighbor queries: Given a vertex $v$, and an index $i\in\left[\Delta\right]$,
output the $i$-th neighbor of $v$, or $\perp$ if $i>\deg(v)$.

  * •

Pair queries: Given two vertices $u$ and $v\in V$, output whether $\\{u,v\\}$
is an edge in $G$ or not.

The or problem on $N$ bits is: Given query access to a bit-string
$\mathbf{x}\in\\{0,1\\}^{N}$, determine whether there exists an $i$ such that
$x_{i}=1$. By query access, we mean that the algorithm can ask for any
$i\in\\{N\\}$ whether $x_{i}$ is $0$ or $1$. It is well known that the
randomized query complexity $R(\textnormal{{or}}_{N})$ is $\Omega(N)$ (see
[20]). We will reduce the following promise version of the problem to
$\Delta$-coloring (which is also known to have randomized query complexity
$\Omega(N)$):

######  Problem A.1 ($\textnormal{{or-one}}_{N}$).

Given query access to a string $\mathbf{x}\in\\{0,1\\}^{N}$ such that the
Hamming weight of $\mathbf{x}$ is at most $1$, determine whether there is an
index $i$ such that $x_{i}=1$.

Let $N=\binom{n}{2}$. The reduction from $\textnormal{{or-one}}_{N}$ to
$\Delta$-coloring is the following: For a bit-string
$\mathbf{x}\in\\{0,1\\}^{N}$, we will define a graph $G$ on the vertex set
$U=\\{u_{1},\ldots,u_{n}\\}\cup V=\\{v_{1},\ldots,v_{n}\\}$. We index
$\mathbf{x}$ as $x_{i,j}$ for $1\leqslant i<j\leqslant n$, and add edges to
$G$ as follows:

  * •

If $x_{i,j}=0$, add the internal edges $\\{u_{i},u_{j}\\}$ and
$\\{v_{i},v_{j}\\}$.

  * •

If $x_{i,j}=1$, add the crossing edges $\\{u_{i},v_{j}\\}$ and
$\\{v_{i},u_{j}\\}$.

Note that the graph $G$ is $(n-1)$-regular (so $\Delta=n-1$). Now, if
$\mathbf{x}=0^{N}$, then the sets $U$ and $V$ have no edges between them, and
$G$ is just two copies of $K_{n}$, and hence not $\Delta$-colorable. If, on
the other hand, $x_{i,j}=1$ for one pair $(i,j)$ then $G$ is two copies of
$K_{n}$ minus an edge, connected by a pair of cross edges, and by Brooks’
Theorem $G$ is $\Delta$-colorable. To finish the reduction, we need to show
that we can simulate each of the queries of the general query model on $G$
with at most a single query on $\mathbf{x}$:

  * •

Degree queries: We always return $n-1$, without looking at any bit of
$\mathbf{x}$.

  * •

Neighbor queries: To get the $j$-th neighbor of $u_{i}$ (or $v_{i}$), we need
to look at the bit:

$\begin{cases}x_{j,i}&\text{if }j<i\\\ x_{i,j+1}&\text{if }i\leqslant
j\leqslant n-1\\\ \end{cases}$

  * •

Pair queries: Assume without loss of generality that the query is for the pair
$(u_{i},v_{j})$ such that $i<j$. Then we can answer it by just looking at the
bit $x_{i,j}$.

And hence, a $o(n^{2})$ query algorithm for $\Delta$-coloring a graph on $2n$
vertices implies a $o(N)$ query algorithm for the or-one problem on
$N=\binom{n}{2}$ bits. Note that we can pad an arbitrary instance of
$\textnormal{{or-one}}_{N}$ to an instance we can reduce with at most a
constant blowup in size, since $(n+1)^{2}\leqslant 2n^{2}$ for all $n$ large
enough.

######  Lemma A.2.

The randomized query complexity of $\Delta$-coloring a graph on $n$ vertices
is $\Omega(n^{2})$ for some choice of $\Delta=\Theta(n)$.

We can take this idea further: Suppose instead that we have $\Theta(n/\Delta)$
instances of or-one on $\binom{\Delta+1}{2}$ bits. In particular, define the
and-or-one problem:

######  Problem A.3 ($\textnormal{{and-or-one}}_{t,m}$).

Given query access to a set of $t$ strings
$\mathbf{x}_{1},\ldots,\mathbf{x}_{t}\in\\{0,1\\}^{m}$, compute:

$\bigwedge_{i=1}^{t}\textnormal{{or-one}}_{m}(\mathbf{x}_{i}).$

Then it is well known that the randomized query complexity of
$\textnormal{{and-or-one}}_{t,m}$ is $\Omega(tm)$ (see [21], [61]). We will
take an instance of and-or-one with $m=\binom{\Delta+1}{2}$ and
$t\in\mathbb{N}$—setting $n=t\cdot 2m$—and reduce it to $\Delta$-coloring a
graph on $2n$ vertices. In particular, the graph will just be the (disjoint)
union of the graphs formed by reducing each of the $\textnormal{{or-one}}_{m}$
instances in the fashion described above. Note that the graph will be
$\Delta$-regular. It is immediate that a $o(n\Delta)$-query algorithm for
$\Delta$-coloring implies a $o(t\cdot\Delta^{2})=o(tm)$-query algorithm for
and-or-one, and we have a contradiction.

######  Lemma A.4.

The randomized query complexity of $\Delta$-coloring a graph on $n$ vertices
is $\Omega(n\Delta)$ for all choices of $100\leqslant\Delta<n/100$.

####  A.2 Streaming Algorithms on Repeated-Edge Streams

In this section, we will show that any $O(1)$ pass algorithm for
$\Delta$-coloring on graph streams with repeated edges needs $\Omega(n\Delta)$
space to color a graph on $n$ vertices and maximum degree $\Delta$. In
particular, we will reduce the tribes problem from communication complexity to
the $\textnormal{{clique}}_{\Delta+1}$ problem. We start by defining the
$\textnormal{{tribes}}_{m,n}$ problem.

######  Problem A.5 ($\textnormal{{tribes}}_{m,n}$).

In the $\textnormal{{tribes}}_{m,n}$ problem, Alice and Bob receive $m$
vectors $\mathbf{x}_{1},\ldots,\mathbf{x}_{m}\in\\{0,1\\}^{n}$ and
$\mathbf{y}_{1},\ldots,\mathbf{y}_{m}\in\\{0,1\\}^{n}$ respectively. They want
to compute the function:

$\bigwedge_{k=1}^{m}\textnormal{{disj}}_{n}(\mathbf{x}_{k},\mathbf{y}_{k}).$

Where $\textnormal{{disj}}_{n}$ is the standard disjoint function that is true
iff its inputs differ in all of their bits.

In words, the problem is just to solve $m$ instances of
$\textnormal{{disj}}_{n}$, and return true only if all of them are disjoint.
By a result of [42], the randomized communication complexity of
$\textnormal{{tribes}}_{m,n}$ is $\Omega(mn)$. We will show a low-
communication protocol for $\textnormal{{tribes}}_{m,n}$ assuming a small-
space algorithm for $\textnormal{{clique}}_{\Delta+1}$, which is defined as
follows:

######  Problem A.6 ($\textnormal{{clique}}_{\Delta+1}$).

Given a graph $G$ as a stream, determine whether or not $G$ contains a
$(\Delta+1)$-clique.

First, we will do a warm-up reduction, from $\textnormal{{disj}}_{N}$ to
clique, which simply asks if the input graph is a clique. Suppose that
$N=\binom{n}{2}$ for some $n$,161616This is easily achieved by blowing up the
universe by at most a constant factor. and we have an instance
$\mathbf{x},\mathbf{y}\in\\{0,1\\}^{N}$ of $\textnormal{{disj}}_{N}$. Then we
can relabel the indices to $(u,v)$ such that $1\leqslant u<v\leqslant n$. Let
$A$ be the set $\\{(i,j)\mid x_{i,j}=1\\}$, and $B$ be the same for
$\mathbf{y}$. Define a graph $G$ on the vertex set
$V=\\{v_{1},\ldots,v_{n}\\}$ as follows: Add the edge $\\{v_{i},v_{j}\\}$ to
$G$ iff $\\{i,j\\}$ is in $\overline{A}\cup\overline{B}$. Note that $A$ and
$B$ are disjoint if and only if $\overline{A}\cup\overline{B}$ is the entire
universe, which is equivalent to $G$ being a clique.

Assume that we have a constant-pass $o(n^{2})$ space algorithm for
$\Delta$-coloring (and hence for clique). Then here is a low-communication
protocol for $\textnormal{{disj}}_{N}$: Alice will form “half” the stream by
taking the edge set $\overline{A}$, and run the streaming algorithm for clique
on it, and communicate the state of the algorithm (using $o(n^{2})$ bits) to
Bob. Bob will then continue running the algorithm on his “half” of the stream
(the edge set $\overline{B}$), and hence finish one pass of the algorithm over
the edges of $G$. If there are additional passes required, Bob will
communicate the state of the algorithm to Alice (again, using $o(n^{2})$ bits)
and the process will repeat. After a constant number of passes, the streaming
algorithm will decide whether $G$ is a clique, and hence if $A$ and $B$ are
disjoint, having used $o(n^{2})\cdot O(1)$ communication. And hence we have
shown the following lemma:

######  Lemma A.7.

There is no constant pass $o(n^{2})$ space streaming algorithm for clique.

We can use the same idea when starting with an instance of
$\textnormal{{tribes}}_{m,k}$ where $m=\binom{\Delta+1}{2}$, and
$k\in\mathbb{N}$171717And setting $n=k\cdot(\Delta+1)$. to rule out a
$o(n\Delta)$ space algorithm for $\textnormal{{clique}}_{\Delta+1}$ (and hence
$\Delta$-coloring). In particular, define the $k$-partite graph $G$ on the
vertex sets $V_{1},\ldots,V_{k}$, such that each $G(V_{i},E_{i})$ is the graph
that is a clique iff $\mathbf{x}_{i}$ and $\mathbf{y}_{i}$ are disjoint.

Then supposing we have a constant pass $o(n\Delta)$ space algorithm for
$\textnormal{{clique}}_{\Delta+1}$, we can use exactly the same low
communication protocol as before: Alice and Bob each construct half of the
graph stream, and to complete a pass exchange the entire state of the
algorithm twice. This implies a $o(n\Delta)=o(k\Delta^{2})=o(mk)$
communication protocol for $\textnormal{{tribes}}_{m,k}$, and we have the
contradiction we desire.

######  Lemma A.8.

There is no constant pass $o(n\Delta)$ space streaming algorithm for
$\Delta$-coloring.

The crucial observation is that in the stream created in the communication
protocol, the edges of $G$ can _repeat_. In particular, if the bit $(i,j)$ is
zero in both $\mathbf{x}$ and $\mathbf{y}$, both Alice and Bob add the edge
$\\{v_{i},v_{j}\\}$ to their halves of the stream. Suppose that our algorithm
for $\Delta$-coloring (and hence clique) is only required to work on graph
streams with no repeated edges. Then the low communication protocol breaks
down completely, and hence it is actually possible to solve the
$\Delta$-coloring problem in $o(n\Delta)$ space.

###### A technical remark:

Note that both of the lower-bounds we prove are for the problem which tests
whether a graph is $\Delta$-colorable, but they also apply to the promise
version of the problem where the graph is guaranteed to be $\Delta$-colorable,
and the task is to output a coloring. In particular, suppose we have a
$\Delta$-coloring algorithm $\mathcal{A}$ on a graph stream, then we can use
it for the reduction from $\textnormal{{disj}}_{N}$ as follows:

  * •

Run $\mathcal{A}$ on the input stream for the graph $G$ with edge set
$\overline{A}\cup\overline{B}$, communicating between Alice and Bob as before.

  * •

If $\mathcal{A}$ fails to output a coloring, then the sets $A$ and $B$ are
disjoint (w.h.p.).

  * •

If $\mathcal{A}$ outputs a coloring, then we need to _test_ it. In particular,
if the coloring is improper, there exists an edge in $G$ that is
monochromatic. Alice and Bob can independently test their halves of the edges
for such an edge, and if they don’t find one, the coloring is valid, and hence
$A$ and $B$ are disjoint.

A similar argument shows that the query lower-bound applies to the promise
version too.

###  Appendix B Missing Proofs from Section 5

In this appendix, we show all the results whose proofs we skipped in Section
5. The common factor between these results is that they are all small
modifications of previous work and are presented here only for completeness.

###### Preliminaries:

We use a standard form of Talagrand’s inequality [64] as specified in [50]. A
function $f(x_{1},\ldots,x_{n})$ is called $c$-Lipschitz iff changing any
$x_{i}$ can affect the value of $f$ by at most $c$. Additionally, $f$ is
called $r$-certifiable iff whenever $f(x_{1},\ldots,x_{n})\geqslant s$, there
exist at most $r\cdot s$ variables $x_{i_{1}},\ldots,x_{i_{r\cdot s}}$ so that
knowing the values of these variables certifies $f\geqslant s$.

######  Proposition B.1 (Talagrand’s inequality; cf. [50]).

Let $X_{1},\ldots,X_{m}$ be $m$ independent random variables and
$f(X_{1},\ldots,X_{m})$ be a $c$-Lipschitz function; then for any $t\geqslant
1$,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\left|{f-\operatorname*{{\mathbb{E}}}\left[f\right]}\right|>t\right)\leqslant
2\exp\left(-\frac{t^{2}}{2c^{2}\cdot m}\right).$

Moreover, if $f$ is additionally $r$-certifiable, then for any $b\geqslant 1$,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\left|{f-\operatorname*{{\mathbb{E}}}\left[f\right]}\right|>b+30c\sqrt{r\cdot\operatorname*{{\mathbb{E}}}\left[f\right]}\right)\leqslant
4\exp\left(-\frac{b^{2}}{8c^{2}r\operatorname*{{\mathbb{E}}}\left[f\right]}\right).$

####  B.1 From Section 5.1

######  Lemma B.2 (Re-statement of Lemma 5.2).

For every sparse vertex $v\in V_{\textnormal{sparse}}$, in the partial
coloring $C_{1}$ of one-shot-coloring,

$\mathsf{avail}_{C_{1}}(v)>(\deg{(v)}-\mathsf{coldeg}_{C_{1}}(v))+\frac{\varepsilon^{2}\cdot\Delta}{2\alpha}$

with high probability, where the randomness is only over the choice of the
lists $L_{1}(v)$.

######  Proof B.3.

We consider the random variable gap that counts the colors assigned (by $x$)
to _at least_ two neighbors of $v$, and retained (in $C_{1}$) by _all_ of
them. Note that if gap is large, we are in good shape: since each color it
counts increases the number of colored neighbors of $v$ by at least $2$, while
decreasing the number of colors available to $v$ by $1$. And hence our aim is
to show that gap is large with high probability.

We do this in a roundabout manner. First, we lower bound the expectation of
gap with that of the random variable $\textsf{gap}^{\prime}$, which counts the
number of colors assigned to _exactly_ two vertices in $N(v)$, and retained by
both of them. The main reason for this is that
$\operatorname*{{\mathbb{E}}}\left[\textsf{gap}^{\prime}\right]$ is easy to
calculate, and large enough for our purposes. In particular, let $F$ be the
set of non-edges between the neighbors of $v$, that is

$F=\left\\{\\{u,w\\}\subset N(v)\mid\\{u,w\\}\notin E(G)\right\\}.$

Then since $v$ is sparse,
$\left|{F}\right|\geqslant\varepsilon^{2}\cdot\Delta^{2}/2$ (by Definition
3.2).

For a color $c\in\left[\Delta\right]$ and a non-edge $f=\\{u,w\\}\in F$, let
$\textsf{gap}^{\prime}_{c,f}$ indicate the event:

  * •

$x(u)=x(w)=c$,

  * •

no other vertex in $N(v)\cup\\{v\\}$ receives the color $c$ from $x$, and

  * •

no vertex in $N(u)\cup N(w)$ receives $c$.

By definition, $\textsf{gap}^{\prime}=\sum_{c,f}\textsf{gap}^{\prime}_{c,f}$.
We have:

Where the first inequality follows because $\left|{N(u)\cup N(w)\cup
N(v)}\right|\leqslant 3\Delta$, and the second because

$\exp\left(-\frac{2}{\Delta}\right)\leqslant
1-\frac{2}{\Delta}+\frac{2}{\Delta^{2}}\leqslant 1-\frac{1}{\Delta}.$

By linearity of expectation,

$\operatorname*{{\mathbb{E}}}\left[\textsf{gap}\right]\geqslant\operatorname*{{\mathbb{E}}}\left[\textsf{gap}^{\prime}\right]\geqslant\underbrace{\vphantom{\frac{\varepsilon^{2}\cdot\Delta^{2}}{2}}\Delta}_{\text{choose
}c}\cdot\underbrace{\frac{\varepsilon^{2}\cdot\Delta^{2}}{2}}_{\text{choose
}f}\cdot\frac{1}{e^{6}\cdot\Delta^{2}}=\frac{\varepsilon^{2}\cdot\Delta}{2e^{6}}.$

Next, we want to show that gap is concentrated around its expectation, and for
once, Chernoff does not suffice. Define the random variable assign which
counts the number of colors _assigned_ (by $x$) to at least two vertices in
$N(v)$, and the random variable lose which counts the number of colors
assigned to at least two vertices in $N(v)$, and lost by _any_ of them. Then
clearly $\textsf{gap}=\textsf{assign}-\textsf{lose}$. We will show that assign
and lose are both concentrated around their means, and this implies that gap
is too.

First, note that assign depends only on the assignment $x(w)$ for all $w$ in
the neighborhood of $v$, that is:

$\textsf{assign}\colon\prod_{w\in N(v)}\left[\Delta\right]\to\mathbb{N}.$

Further, it is $1$-Lipschitz – changing $x(w)$ from $c$ to $c^{\prime}$ can:

  * •

Make it so $c$ occurs only once (instead of twice) in $N(v)$, decreasing
assign by $1$.

  * •

Make it so $c^{\prime}$ occurs twice (instead of once) in $N(v)$, increasing
assign by $1$.

And hence the net change to assign from changing $x(w)$ is at most $1$ in
absolute value. Then by the first part of Talagrand’s Inequality (Proposition
B.1, with $m=\Delta$, $c=1$, and
$t=\frac{\varepsilon^{2}\cdot\Delta}{20e^{6}}$) we have:

Which for $\Delta=\Omega(\log^{5}n)$ (the $\Omega$ hides a monstrous
constant), is $1/\mbox{\rm poly}(n)$. Note that our choice of $t$ is $1/10$-th
of the lower bound on the expected value of gap.

The same argument does not work for lose—the random variable depends on the
$2$-hop neighborhood of $v$, which has size roughly $\Delta^{2}$, and hence
the bound we get above is too weak. However, note that in addition to being
$2$-Lipschitz, lose is also $3$-certifiable. More concretely, let $W$ denote
the $2$-hop neighborhood of $v$, then:

  * •

Changing $x(w)$ for some $w$ in $W$ can change the contribution of at most $2$
colors to lose: the old and the new color assigned by $x$ to $w$. Hence lose
is $2$-Lipschitz.

  * •

For any $s$, to get $\textsf{lose}\geqslant s$, we need to set $x(\cdot)$ for
three vertices (two neighbors of $v$, and one of their common neighbors) to
$i$, for $i\in\left[s\right]$.

Then by second part of Talagrand’s Inequality (Proposition B.1, with $c=2$,
$r=3$, $b=\frac{\varepsilon^{2}\cdot\Delta}{20e^{6}}$):

Crudely, we upper bound lose (and hence
$\operatorname*{{\mathbb{E}}}\left[\textsf{lose}\right]$) by $\Delta/2$, to
give us:

Which with $\Delta=\Omega(\log^{5}n)$ (and $\Omega$ doing an even braver job)
is $1/\mbox{\rm poly}(n)$.

Taking the union of the bad events (i.e. either assign or lose deviates too
much from its mean), and applying the triangle inequality, we have that with
high probability:

$\textsf{gap}>\operatorname*{{\mathbb{E}}}\left[\textsf{gap}\right]-\frac{\varepsilon^{2}\cdot\Delta}{10e^{6}}-O(\sqrt{\Delta}).$

And hence combining with the lower bound on
$\operatorname*{{\mathbb{E}}}\left[\textsf{gap}\right]$ we found earlier,
$\textsf{gap}>\frac{\varepsilon^{2}\cdot\Delta}{2000}$ with high probability.

####  B.2 From Section 5.3

######  Lemma B.4 (Re-statement of Lemma 5.7).

With high probability, there exists a proper partial $\Delta$-coloring $C$
that is an extension of $C_{2}$ and colors all remaining vertices in
$V_{\textnormal{sparse}}$ using only the colors in the lists $L_{3}(v)$ for
sparse vertices $v\in V_{\textnormal{sparse}}$ (and thus the randomness is
also only over these lists).

######  Proof B.5.

Let $C$ initially be the coloring $C_{2}$. We will color the vertices of
$V_{\textnormal{sparse}}$ greedily by updating $C$. That is, we iterate over
$V_{\textnormal{sparse}}$ in arbitrary order, and if a vertex $v$ is uncolored
in $C$, we pick a color in $L_{3}(v)$ which does not conflict with any of its
neighbors in $H$, and set $C(v)$ to it. Using the randomness of $L_{3}(v)$,
and conditioning on the high probability event of Lemma 5.2:

######  Claim 26.

With high probability, for each vertex $v\in V_{\textnormal{sparse}}$, and any
partial coloring $C$ that extends $C_{1}$, there exists a color $c\in
L_{3}(v)$ that is not used in $N_{H}(v)$ by $C$.

We would like to show that $\mathsf{Avail}_{C}(v)$ and $L_{3}(v)$ have a
nonzero intersection with high probability. Since $v$ is sparse, by Lemma 5.2
we have:

$\mathsf{avail}_{C}(v)>(\deg{(v)}-\mathsf{coldeg}_{C_{1}}(v))+\frac{\varepsilon^{2}\cdot\Delta}{2\alpha}$

Which implies that even if the entire neighborhood of $v$ is colored by $C$,
there are still $\frac{\varepsilon^{2}}{2\alpha}\cdot\Delta$ colors available
for $v$ to use.

Since each color from $\mathsf{Avail}_{C}(v)$ is sampled into $L_{3}(v)$
independently with probability $\frac{100\alpha\cdot\log
n}{\varepsilon^{2}\cdot\Delta}$,

concluding the proof. And hence the greedy algorithm can color
$V_{\textnormal{sparse}}$. Note that this algorithm can be implemented
efficiently using the information we gathered in Section 4. In particular,
since $C$ only assigns colors from $L(v)$ to $v$, it is enough to check for
conflicts in $H$ while coloring from $L_{3}(v)$.

####  B.3 From Section 5.4

######  Lemma B.6 (Re-statement of Lemma 5.9).

For a holey almost-clique $K$, and any partial $\Delta$-coloring $C$ outside
$K$, there exists, with high probability, a coloring $C^{\prime}$ which
extends $C$ to $K$ such that $C^{\prime}(v)\in L_{4}(v)$ for all $v\in K$.

The main thing we want to exploit is that $K$ has a lot of non-edges, since we
can assign the same color to both endpoints of a non-edge. One easy way to do
this for many non-edges simultaneously is to generate a “matching” of non-
edges, which we do via the following algorithm:

Input: The input graph $G$, an almost-clique $K$, the partial coloring $C$,
and the list $L_{4,i}(v)$ for each $v$.

  1. $(i)$

Initialize $C^{\prime}\leftarrow C$.

  2. $(ii)$

Let $F=\\{f_{1},\ldots,f_{t}\\}$ be the set of non-edges in $K$.

  3. $(iii)$

For each color $c\in\left[\Delta\right]$: If there is a non-edge
$f=\\{u,v\\}\in F$ such that $c\in L_{4,i}(u)\cap L_{4,i}(v)$, and $c$ is not
used in the neighborhood of $u$ or $v$, then:

     * •

Assign $C^{\prime}(u)\leftarrow c$ and $C^{\prime}(v)\leftarrow c$.

     * •

Add $f$ to $M$.

     * •

Remove all non-edges incident on $f$ from $F$.

Algorithm 8 The colorful-matching algorithm.

It follows immediately that $M$ is a matching; we will show that for holey
cliques, $M$ is _large_ with constant probability.

######  Lemma B.7.

If $K$ is a holey clique, Algorithm 8 produces a matching of size
$\ell~{}=~{}\frac{t}{10^{6}\varepsilon\Delta}$ with probability at least
$1/2$.

######  Proof B.8.

We define:

  * •

$\textsf{Present}(c)$ as the set of non-edges present in $F$ when we encounter
color $c$ in line (ii) of Algorithm 8. Let $\textsf{present}(c)$ denote
$\left|{\textsf{Present}(c)}\right|$.

  * •

A color $c$ is _successful_ if we add assign it to a non-edge during Algorithm
8.

Note that the number of successful colors is exactly the size of $M$, and
hence we would like to show that many colors succeed. To do so, we show that
$\textsf{present}(\cdot)$ is large for many colors. In particular, we say that
a color $c$ is _heavy_ if it has $\textsf{present}(c)\geqslant t/2$, and have
the following claim:

######  Claim 28.

There are at least $\Delta/2$ heavy colors.

######  Proof B.9.

For a non-edge $f=\\{u,v\\}$, define $\textsf{Blocked}(f)$ to be the set of
colors used by $C$ to color the neighbors of $u$ or $v$ outside $K$. By
property item $iii)$. of Definition 3.3, the number of neighbors of $u$ or $v$
(and hence the number of colors used by $C$ to color them) is at most
$20\varepsilon\Delta$. As a result, at the beginning of the algorithm:

$\sum_{f\in F}\left|{\textsf{Blocked}(f)}\right|\leqslant t\cdot
20\varepsilon\Delta.$

This means that on average, each color occurs in $\textsf{Blocked}(f)$ for at
most

$t\cdot 20\varepsilon\Delta\cdot 1/\Delta=20\varepsilon t$

non-edges $f$. By Markov’s Inequality, there are at most $\Delta/2$ colors $c$
which occur in $\textsf{Blocked}(f)$ for more than $40\varepsilon t$ non-edges
$f$. Hence there are at least $\Delta/2$ colors $c$ which are _not blocked_
for at least $t-40\varepsilon t\geqslant 9/10\cdot t$ non-edges in $F$—at the
beginning of the algorithm.

How many of these non-edges remain in $\textsf{Present}(c)$ when we look at
$c$? Upon adding the non-edge $\\{u,v\\}$ to $M$, we remove all non-edges
incident on $u$ or $v$ from $F$. Since each $u\in K$ has at most
$10\varepsilon\Delta$ non-neighbors in $K$ (property $ii)$. of Definition
3.3), each non-edge added to $M$ removes at most $20\varepsilon\Delta$ edges
from $\textsf{Present}(c)$. Because the algorithm has already succeeded if
$\left|{M}\right|$ becomes larger than $\ell$, the number of edges removed
from $\textsf{Present}(c)$ is at most $\ell\cdot 20\varepsilon\Delta$ in
total, which is $<t/10$. Hence there are at least $\Delta/2$ colors $c$ with
$\textsf{present}(c)\geqslant 8/10\cdot t\geqslant t/2$.

Regrouping, we have shown that there are many colors in $\left[\Delta\right]$
that can be assigned to many non-edges in $F$. Next, we would like to show
that for each of these heavy colors $c$, the probability that $c$ is in
sampled by both endpoints of a non-edge in $\textsf{Present}(c)$ is high.

######  Claim 29.

For a heavy color $c$, .

The color $c$ is successful if there is least one non-edge
$\\{u,v\\}\in\textsf{Present}(c)$ such that $c\in L_{4,i}(u)\cap L_{4,i}(v)$.
Using the inclusion exclusion principle, and cutting out terms of “order” more
than $2$:

$\displaystyle\geqslant\sum_{\\{u,v\\}\in\textsf{Present}(c)}$
$\displaystyle-\sum_{f,g\,\in\,\textsf{Present}(c)}$

The first term is easy to compute exactly: $c$ belongs to both lists with
probability $q^{2}$, so

$\sum_{\\{u,v\\}\in\textsf{Present}(c)}$

For the second term, we have to consider two cases:

  * •

$\left|{f\cup g}\right|=3$: The probability that $c$ belongs to $L_{4,i}(w)$
for 3 vertices $w$ is $q^{3}$. After picking $f=\\{u,v\\}$ from
$\textsf{Present}(c)$, there are at most $20\varepsilon\Delta$ choices for the
third vertex, and hence the total contribution of terms of this type is at
most

$\textsf{present}(c)\cdot 20\varepsilon\Delta\cdot q^{3}.$

  * •

$\left|{f\cup g}\right|=4$: The probability that $c$ belongs to the list of
$4$ vertices is $q^{4}$. And there are at most $\textsf{present}(c)^{2}$ ways
to pick a $2$-set of non-edges. So the total contribution of these terms is at
most

$\textsf{present}(c)^{2}\cdot q^{4}.$

Adding everything up, we get:

$\displaystyle\geqslant\textsf{present}(c)\cdot q^{2}-\textsf{present}(c)\cdot
10\varepsilon\Delta\cdot q^{3}-\textsf{present}(c)^{2}\cdot q^{4}$
$\displaystyle\geqslant 9/10\cdot\textsf{present}(c)\cdot
q^{2}-\textsf{present}(c)^{2}\cdot q^{4}$ (since
$q=\frac{1}{100\sqrt{\varepsilon}{\Delta}}$ and thus $10\varepsilon\Delta\cdot
q<1/10$ for $\varepsilon<1$) $\displaystyle\geqslant\textsf{present}(c)\cdot
q^{2}\cdot\left(9/10-20\varepsilon\Delta^{2}\cdot q^{2}\right)$ (since
$\textsf{present}(c)\leqslant\left|{F}\right|\leqslant
20\varepsilon\Delta^{2}$ by property $ii)$. of Definition 3.3)
$\displaystyle\geqslant 8/10\cdot\textsf{present}(c)\cdot q^{2}\text{\ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (since
$q=\frac{1}{100\sqrt{\varepsilon}\Delta}$, $20\varepsilon\Delta^{2}\cdot
q^{2}=1/200$)}$
$\displaystyle\geqslant\frac{t}{10^{5}\cdot\varepsilon\Delta^{2}},$

concluding the proof.

Finally, we are ready to prove the lemma itself. Let $\theta=10^{-5}\cdot
t/\varepsilon\Delta^{2}$ (the RHS of Claim 29); note that $\theta<1$ because
$t\leqslant\left|{F}\right|\leqslant 20\varepsilon\Delta^{2}$. Let $Z$ be a
random variable with the binomial distribution
$\mathcal{B}\left(\Delta/2,\theta\right)$. Note that we can couple each
Bernoulli trial used to determine $Z$ with a heavy color succeeding – since
there are at least $\Delta/2$ of them, they succeed with probability at least
$\theta$, and two different colors are independent of each other. Hence $Z$ is
a lower bound for $\left|{M}\right|$. We follow our usual formula:

$\operatorname*{{\mathbb{E}}}\left[Z\right]=\Delta/2\cdot\theta=10^{-5}\cdot
t/2\varepsilon\Delta.$

And with an application of Chernoff Bound (Proposition 3.1, with
$\delta=1/2$):

And hence with probability at least $1/2$,

$\left|{M}\right|\geqslant Z\geqslant 10^{-5}\cdot
t/8\varepsilon\Delta>10^{-6}\cdot t/\varepsilon\Delta=\ell.$

This concludes the proof.

Now, since we run Algorithm 8 for $\beta$ independent sets lists
$\\{L_{4,i}(v)\mid v\in V\\}$, we get a non-edge matching $M$ of size
$\ell=t/\varepsilon\Delta$ from one of the runs with high probability. We keep
the coloring assigned to this largest non-edge edge matching, and hence have
the following lemma:

######  Lemma B.10.

Suppose $K$ is a holey almost-clique, with $t\geqslant
10^{7}\cdot\varepsilon\Delta$ non-edges inside it. Then for any coloring $C$
outside $K$, with high probability there is an extension $C^{\prime}$ of $C$
which:

  * •

Colors $2\cdot\frac{t}{10^{6}\cdot\varepsilon\Delta}$ vertices of $K$.

  * •

Uses only $\frac{t}{10^{6}\cdot\varepsilon\Delta}$ colors inside $K$, and
further for each $v\in K$ that it colors, uses a color from $L_{4}(v)$.

Let us pause for a moment, and consider why we did all this work. Lemma B.10
tells us that Algorithm 8 colors _some_ number of vertices in $K$, using only
half that many unique colors. As in the case of sparse vertices, this creates
enough of a gap between available colors and the remaining degree of each
vertex in $K$ such that an available color is sampled in $L_{4}(v)$ with high
probability. This is exactly what we need to prove Lemma 5.9.

######  Proof B.11 (Proof of Lemma 5.9).

Let $C^{\prime}$ be the partial coloring obtained from Lemma B.10. Then we
define the base and sampled palette graphs $\mathcal{G}_{\textnormal{{Base}}}$
and $\mathcal{G}_{\textnormal{{Sample}}}$ (Definitions 3.8 and 3.9) with:

  * •

$\mathcal{L}$ as the set of vertices of $K$ _not_ colored by $C^{\prime}$.

  * •

$\mathcal{R}$ as the set of colors _not_ used by $C^{\prime}$ in $K$.

  * •

$S(v)=L_{4}^{*}(v)$ for each $v\in\mathcal{L}$.

We will show that $\mathcal{G}_{\textnormal{{Base}}}$ satsifies the conditions
in Lemma 3.10, and hence $\mathcal{G}_{\textnormal{{Sample}}}$ has an
$\mathcal{L}$-perfect matching with high probability, and hence $C^{\prime}$
can be extended to $(L_{4}\cup L_{4}^{*})$-color all of $K$. In the same order
as the lemma:

  1. $(i)$

For $m:=\mathcal{L}$, $m\leqslant\left|{\mathcal{R}}\right|\leqslant 2m$: To
get the first inequality, we rewrite $\left|{\mathcal{L}}\right|$ and
$\left|{\mathcal{R}}\right|$ in terms of $K$ and the vertices and colors
removed by $C^{\prime}$:

$\left|{\mathcal{L}}\right|=\left|{K}\right|-\frac{2t}{10^{6}\cdot\varepsilon\Delta},\left|{\mathcal{R}}\right|=\Delta-\frac{t}{10^{6}\cdot\varepsilon\Delta}.$

Note that if $\left|{K}\right|\geqslant\Delta+1+k$, the number of non-edges
inside $K$ (that is, $t$) is at least $k\cdot\Delta$. Then the number of
vertices removed far outstrips the number of colors, in particular:

$\left|{\mathcal{L}}\right|=\Delta+1+k-\frac{2k}{10^{6}\cdot\varepsilon}\leqslant\Delta-k,\left|{\mathcal{R}}\right|=\Delta-\frac{k}{10^{6}\cdot\varepsilon}.$

Which makes $\left|{\mathcal{L}}\right|\leqslant\left|{\mathcal{R}}\right|$
for $k\geqslant 1$, because $\frac{1}{10^{6}\cdot\varepsilon}>2$. On the other
hand, if $K=\Delta+1$, since $t\geqslant 10^{7}\cdot\varepsilon\Delta$,

$\left|{\mathcal{R}}\right|-\left|{\mathcal{L}}\right|=\frac{10^{7}\cdot\varepsilon\Delta}{10^{6}\cdot\varepsilon\Delta}-1\geqslant
9.$

To get the second inequality, first note that $m\geqslant 2/3\cdot\Delta$.
This is because the maximum number of non-edges in $K$ is
$(2\Delta)\cdot(10\varepsilon\Delta)=20\varepsilon\Delta^{2}$ (by property
$ii)$. of Definition 3.3), and hence the number of vertices in $\mathcal{L}$
is at least

$(1-5\varepsilon)\Delta-\frac{40\varepsilon\Delta^{2}}{10^{6}\cdot\varepsilon\Delta}\geqslant
2/3\cdot\Delta.$

Then since $\left|{R}\right|\leqslant\Delta$ we are done.

  2. $(ii)$

Each vertex $v\in\mathcal{L}$ has
$\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant 2/3\cdot m$: Each vertex
$v$ in $\mathcal{L}$ may have up to $10\varepsilon\Delta$ edges out of $K$ (in
$G$), hence blocking $10\varepsilon\Delta$ colors in $\mathcal{R}$ for $v$.
Since all the remaining colors are available to $v$,

$\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{R}\right|-10\varepsilon\Delta\geqslant
m-15\varepsilon\cdot m\geqslant 2/3\cdot m.$

Where the second inequality follows from part (i).

  3. $(iii)$

For every set $A\subset\mathcal{L}$ of size $\left|{A}\right|\geqslant m/2$,
we have $\sum_{v\in
A}\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{A}\right|\cdot
m-m/4$; recall that for any $v\in\mathcal{L}$:

$\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)\geqslant\left|{R}\right|-(\Delta+1)+\left|{K}\right|-\overline{\deg}_{K}({v}).$

Let $T:=\frac{t}{10^{6}\cdot\varepsilon\Delta}\geqslant 10$. Summing the
inequality above over $v\in A$, we get:

$\displaystyle\sum_{v\in A}\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)$
$\displaystyle\geqslant\sum_{v\in
A}\left(\left|{R}\right|-(\Delta+1)+\left|{K}\right|-\overline{\deg}_{K}({v})\right)$
$\displaystyle=\sum_{v\in
A}(\underbrace{\Delta-T}_{\left|{R}\right|}-(\Delta+1)+\underbrace{\left|{\mathcal{L}}\right|+2T}_{\left|{K}\right|}-\overline{\deg}_{K}({v}))$
$\displaystyle=\sum_{v\in
A}\left(\left|{L}\right|-\overline{\deg}_{K}({v})+T-1\right)$
$\displaystyle=\left|{A}\right|\cdot(m+T-1)-\underbrace{\sum_{v\in
A}\overline{\deg}_{K}({v})}_{\leqslant 2t}>\left|{A}\right|\cdot m.$

Where the last inequality follows from

$(T-1)\cdot\left|{A}\right|\geqslant
T/2\cdot\left|{A}\right|\geqslant\frac{tm}{10^{6}\cdot
4\varepsilon\Delta}\geqslant\frac{t\Delta}{10^{6}\cdot
6\varepsilon\Delta}\geqslant 5t.$

And now by the promised application of Lemma 3.10,
$\mathcal{G}_{\textnormal{{Sample}}}$ has an $\mathcal{L}$-perfect matching,
and we are done.