Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Assadi, Sepehr; Yazdanyar, Helia

doi:10.4230/LIPIcs.ICALP.2026.16

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Sepehr Assadi

School of Computer Science, University of Waterloo, Canada Helia Yazdanyar

School of Computer Science, University of Waterloo, Canada

Abstract

A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree $\Delta$ can be properly colored with $O(\Delta/\ln\Delta)$ colors, improving upon the “greedy bound” of $\Delta+1$ coloring in general graphs. This coloring can also be found in polynomial time.

We present an algorithm for maintaining an $O(\Delta/\ln\Delta)$ coloring of a dynamically changing triangle-free graph that undergoes edge insertions and deletions. The algorithm is randomized and on $n$ -vertex graphs has amortized update time of $\Delta^{o(1)}\log{n}$ per update with high probability, even against an adaptive adversary.

A key to the analysis of our algorithm is an application of the entropy compression method that to our knowledge is new in the context of dynamic algorithms. This technique appears general and is likely to find other applications in dynamic problems and thus can be of its own independent interest.

Keywords and phrases:

Dynamic graphs - Graph coloring - Dynamic entropy compression

Category:

Track A: Algorithms, Complexity and Games

Funding:

Sepehr Assadi: Supported in part by an NSERC Discovery Grant and a Faculty of Math Research Chair grant.

Helia Yazdanyar: Supported in part by a Cheriton Scholarship from School of Computer Science, a Cotton Family Women in Mathematics Graduate Scholarship, and SA’s NSERC Discovery Grant.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Dynamic graph algorithms

Related Version:

Full Version: https://arxiv.org/abs/2604.20648

Acknowledgements:

We are thankful to Bernhard Haupler and Thatchaphol Saranurak for illuminating discussions.

DOI:

10.4230/LIPIcs.ICALP.2026.16

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Graph coloring is one of the most studied topics in graph theory with a wide range of applications in computer science. Let $G=(V,E)$ be an $n$ -vertex undirected graph with maximum degree $\Delta$ . For any integer $c\geqslant 1$ , a (proper) $c$ -coloring of $G$ is an assignment of colors from $\left\{1,\ldots,c\right\}$ to the vertices of the graph so that no edge is monochromatic. It is easy to see that every graph admits a $(\Delta+1)$ coloring which can be found via a simple greedy algorithm in linear time: color the vertices one by one in an arbitrary order and for each one, choose a color not assigned to any of its already colored neighbors, which always exist by the pigeonhole principle.

Nevertheless, one can almost always find a coloring with fewer colors. Brooks’ theorem [15] states that the only (connected) graphs that do need $\Delta+1$ colors are $(\Delta+1)$ -cliques (and odd cycles only when $\Delta=2$ ); all other graphs can be colored with $\Delta$ colors. As already pointed out by Vizing in [41], this result is just the tip of the iceberg and there is a vast body of work in graph theory with the general theme of coloring graphs with “fewer” than $\Delta$ colors based on how “far” they get from being a clique; see, e.g., [28, 27, 36, 38, 3, 30, 31, 4, 29, 14]. A central result here is a seminal theorem of Johansson [27] that proves that triangle-free graphs are $O(\Delta/\ln\Delta)$ colorable. This bound is asymptotically optimal and has been since sharpened to $(1+o(1))\Delta/\ln{\Delta}$ colors by Molloy [29] (see also [25, 35, 7, 1]).

We study coloring of triangle-free graphs in the dynamic setting, wherein the graph undergoes edge insertions and deletions and we want to maintain a proper coloring after every update. There has been extensive interest in dynamic algorithms for graph coloring problems and specifically $(\Delta+1)$ coloring [10, 12, 24, 5, 20]. The state of the art for $(\Delta+1)$ coloring are randomized algorithms with amortized expected update time of $O(1)$ against oblivious adversaries [12, 24] and $\widetilde{O}(n^{2/3})$ against adaptive adversaries [20]¹¹1An oblivious adversary fixes the set of updates to the graph before presenting them to the algorithm, whereas an adaptive adversary may present each update to the graph based on the output of the algorithm on previous updates; see [6, 8, 5] for more discussion on the different types of adversary.. Other variants of dynamic graph coloring have also been studied including arboricity-dependent coloring [16, 18] and edge coloring [19, 17, 11]. However, to our knowledge, there have been no prior work on dynamic algorithms for coloring triangle-free graphs. This is in contrast to related models such as static [25, 29, 1], parallel [21], distributed [35], streaming [2] and sublinear time [2] algorithms. We address this gap in our paper.

Before getting to our results, let us mention what existing static algorithms can imply for the problem in dynamic graphs. Previously, [25, 29] provided $\widetilde{O}(n\Delta^{2})$ time algorithms²²2Throughout, we use the standard notation $\widetilde{O}(f):=O(f\cdot\mbox{\rm poly}\log{f})$ to suppress logarithmic factors. for $O(\Delta/\ln{\Delta})$ coloring of triangle-free static graphs. By running this algorithm after each $\Theta(\Delta/\ln{\Delta})$ updates and using new colors in the meantime to keep a proper coloring, this implies a dynamic algorithm with $\widetilde{O}(n\Delta)$ update time. Using the sublinear time algorithm of [2] in place of the static algorithms can further reduce this to $\min{(n^{1+o(1)},n^{2+o(1)}/\Delta^{2})}$ update time. It is worth comparing this state of affairs with the trivial dynamic algorithm for $(\Delta+1)$ coloring that recolors at most one vertex per update, by spending $O(\Delta)$ time to iterate over its neighbors and find an available color. This strategy however does not work for $O(\Delta/\ln\Delta)$ coloring of triangle-free graphs given there is no reason why one can greedily extend such a coloring to a new vertex.

1.1 Our Contributions

We present a randomized algorithm for maintaining an $O(\Delta/\ln\Delta)$ coloring of triangle-free graphs in $\Delta^{o(1)}\log{n}$ amortized update time.

Result 1.

There is an algorithm that for any constant $\gamma\in(0,1)$ , maintains an $O_{\gamma}(\Delta/\ln{\Delta})$ coloring of any $n$ -vertex fully dynamic triangle-free graph in $O(\Delta^{\gamma}\log{n})$ amortized update time. The algorithm is randomized and works with high probability against an adaptive adversary (against an oblivious adversary, the update time improves to $O(\Delta^{\gamma})$ time).

Result 1 provides the first non-trivial dynamic algorithm for coloring triangle-free graphs, and goes way below the benchmark of re-running static algorithms after a fixed number of updates. Indeed, by letting $\gamma\rightarrow 0$ , we can reduce the update time to $\Delta^{o(1)}\log{n}$ time while maintaining an $O(\Delta/\ln{\Delta})$ coloring of the graph. It is worth contrasting this bound with the state-of-the-art bound of $\widetilde{O}(n^{2/3})$ amortized update time for $(\Delta+1)$ coloring of arbitrary graphs.

A key component of our main algorithm in Result 1 is a dynamic algorithm for recoloring the graph after each update analogous to the trivial $O(\Delta)$ update time algorithm for $(\Delta+1)$ coloring. Unlike greedy coloring, our algorithm is based on a local search strategy, that on average, requires spending $O(\Delta^{2}\log{n})$ time per update.

Result 2.

For any constant $\varepsilon\in(0,1)$ , there is an algorithm for maintaining a $(1+\varepsilon)\Delta/\ln{\Delta}$ coloring of $n$ -vertex fully dynamic triangle-free graphs with maximum degree $\Delta$ (sufficiently large as a function of $\varepsilon$ ). The algorithm is randomized and with high probability has amortized update time of $O(\Delta^{2}\log{n})$ even against adaptive adversaries (against an oblivious adversary, the update time improves to $O(\Delta^{2})$ time).

Result 2 can be seen as a dynamic version of the Molloy’s breakthrough [29] that proves triangle-free graphs are $(1+o(1))\Delta/\ln{\Delta}$ colorable, sharpening the leading constants in the long line of work on this problem [27, 30, 25, 35, 4]. Our algorithm is inspired by Molloy’s proof of using the entropy compression method, originally introduced by Moser [32] and Moser and Tardos [33] in their seminal work on algorithmic Lovasz Local Lemma.

Our techniques

Employing Molloy’s entropy compression directly only leads to a dynamic algorithm with $O(n\Delta)$ update time (see [29]). However, we show how to make the entropy compression dynamic, which to our knowledge, is new in this context (for readers familiar with this technique, we achieve this by considering the interaction of the randomized dynamic algorithm and adversary jointly as a compression algorithm, logging the “standard” parts of the technique combined with dynamic changes to the graph as part of the compression, and design a recovery algorithm that given this log can recover the original random bits despite the dynamic changes to the graph; see Section 3.2 for more details). Beside this, Molloy uses entropy compression to reduce the problem to a list-coloring problem of Reed [37] (see also [39]). For our purpose, this reduction is not sufficient as we do not know how to solve Reed’s problem dynamically. Instead, we use (dynamic) entropy compression to reduce the problem to the $(\Delta+1)$ -coloring problem and then can use the $O(\Delta)$ update time dynamic algorithm for the problem.

To prove Result 1 from Result 2, we borrow an idea originally due to [10] for $(1+o(1))\Delta$ coloring of arbitrary dynamic graphs. The general approach is to maintain a hierarchy of vertex partitions of the graph, and ensure that at each level of the hierarchy, each vertex belongs to a partition with “few” other neighbors in its own part (roughly speaking, we would like to dynamically partition vertices into $b$ groups in each level, so each vertex $v$ have $\approx\deg(v)/b$ neighbors in its group). We implement this by designing a family of recursive algorithms with improved update times whose base case is our algorithm in Result 2. This recursive approach, as opposed to the “iterative” argument of [10], allows us to better control the parameters involved and extend the argument to $O(\Delta/\ln{\Delta})$ coloring, which in particular, is a non-linear function of vertex degrees.

Perspective: dynamic entropy compression

Entropy compression, as argued by [40] – who also coined this term for the techniques of [32, 33] – is a unique type of potential function argument. Suppose we want a coloring of a graph that satisfy a certain “local” constraint, e.g., the constraint of each vertex depends on colors of its neighbors. Then, we start with an arbitrary coloring of the graph, and then as long as we find a vertex $v$ that violates its constraint, we randomly and locally change the colors of vertices around it. Suppose we could even say that “with large probability” this random change fixes the constraint for the vertex $v$ . Can we also argue that repeating this process enough number of times fixes all constraints? The challenge is that fixing constraint of a single vertex may lead to many other constraints for other vertices to be violated now. Entropy compression is precisely a method to keep track of the “progress” made by this algorithm in a potential-function type argument. At its core, it argues that if we can run this process for a large number of times, we will be able to compress a truly random string to a summary of much smaller length, which is information-theoretically impossible.

Potential functions appear quite frequently in the analysis of dynamic graph algorithms. Yet, to our knowledge, entropy compression is curiously omitted from the standard toolkit in this literature. Our work shows that this technique can be naturally extended to analyze dynamic graph algorithms as well. We especially find this interesting as it allows for analyzing randomized algorithms against adaptive adversaries in a new way. Most adaptive dynamic algorithms use randomization to run fast sublinear time algorithms once every fixed number of updates (this allows them to address the correlation between randomness and adaptive adversary’s update by using fresh randomness in the analysis); see, e.g., the adaptive dynamic algorithms for $(\Delta+1)$ coloring [5, 20]. In contrast, dynamic entropy compression allows us to continuously use randomness in the algorithm and still analyze its performance against an adaptive adversary, similar to how one typically does with a potential function in a deterministic algorithm (the only other technique of this nature we are aware of is proactive resampling introduced in [9, 13] although the similarities here are more conceptual than technical). We believe that this viewpoint is an important (non-technical) contribution of our paper as it may pave the way for obtaining more efficient dynamic algorithms for other fundamental graph problems as well.

Independent and concurrent works

Parallel to us, [23] further developed the proactive resampling technique of [9, 13]. Among many other interesting results, they also presented a fully dynamic $O(\Delta/\ln{\Delta})$ coloring algorithm for triangle free graphs with update time of $n^{1/2+o(1)}$ by “dynamizing” the sublinear time algorithm of [2]. Technique-wise, our work and [23] appear to be entirely disjoint.

More relatedly, [22] also observed that entropy compression gives a recipe for designing dynamic algorithms and used this to prove a wide class of local search algorithms extend as is to the fully dynamic setting. As a corollary of their techniques, they also obtained an entropy compression based dynamic algorithm for coloring triangle-free graphs similar to our Result 2. Their results are quite more general than ours in scope and span various applications of algorithmic Lovasz Local Lemma and beyond. But, for the specific problem at hand, their general framework gives an $\widetilde{O}(\Delta^{3})$ update time algorithm for $6\Delta/\ln{\Delta}$ coloring of triangle-free graphs, which is quantitatively weaker than Result 2 (the extension of our results to $\Delta^{o(1)}\log{n}$ update time in Result 1 is using a separate set of techniques that is missing from [22]). At a technical-level, our dynamic entropy compression works by “logging dynamic updates” whereas [22] do a union bound over all possible choices of adversary, which are different perspectives on the same general idea.

2 Preliminaries

Notation.

For any integer $b\geqslant 1$ , define $[b]:=\left\{1,\cdots,b\right\}$ . For a graph $G=(V,E)$ , we use $N(v)$ to denote the neighbors of $v\in V$ , $\deg(v)=\left|{N(v)}\right|$ to denote the degree of $v$ , and $B(v,r)$ to denote the ball of radius $r$ around $v$ , i.e., all vertices that are at distance at most $r$ from $v$ . A partial coloring of a graph $G=(V,E)$ is a function $\varphi:V\to\mathcal{C}\cup\{\perp\}$ , where $\mathcal{C}$ is a set of colors and $\perp$ denotes an uncolored vertex, also referred to as a free vertex. A partial coloring $\varphi_{t}$ is said to be proper if no edge is monochromatic, however vertices assigned color $\perp$ are exempt, namely, are allowed to be adjacent to each other.

Dynamic graphs.

We denote the static vertex set of the underlying $n$ -vertex graph by $V:=[n]$ . Let $\mathcal{G}=(G_{0},G_{1},\cdots,G_{t},\cdots)$ be the sequence of dynamic graphs presented to the algorithm: the initial graph $G_{0}$ is empty and each graph $G_{t}$ is obtained from the previous graph $G_{t-1}$ by inserting or deleting a single edge $e_{t}=(u_{t},v_{t})$ . We use $G_{t}:=(V,E_{t})$ to denote the graph at the $t$ -th step; $N_{t}(v)$ , $\deg_{t}(v)$ , and $B_{t}(v,r)$ for any $v\in V$ and $r\geqslant 0$ are defined analogously with respect to $G_{t}$ .

As is common in this context, we assume $\Delta$ is known a priori and every vertex has degree at most $\Delta$ throughout the updates. We also assume the number of updates is $\Omega(n)$ as otherwise, there will be vertices that do not even receive a single update and are hence redundant³³3This is relevant when we would like to achieve a “with high probability” guarantee for some aspect of the algorithm (say, runtime). If the updates are much smaller than $n$ , then one naturally cannot expect a probability bound based on $n$ to hold (think of padding an arbitrary graph with “near infinitely many” vertices)..

An oblivious adversary fixes the choices of graphs in $\mathcal{G}$ before presenting them to the algorithm whereas an adaptive adversary can choose each graph $G_{t}$ based on the output of the algorithm on prior graphs $G_{1},\ldots,G_{t-1}$ (in our case, we assume even the prior random coin tosses of the algorithm are available to the adversary). This adversary can be modeled as a game between the dynamic algorithm and an oracle $\mathcal{O}_{A}$ that at each time step $t$ receives the random coins used along with the current coloring and outputs the next update.

Finally, the recourse of a dynamic graph coloring algorithm is the worst-case number of vertices whose colors have changed by the algorithm after each single update.

Balls into bins

We use the following variant of balls and bins experiments. Consider a set of $d$ balls and $b$ bins $\mathcal{B}=\{B_{1},\ldots,B_{b}\}$ . For each ball $i\in[d]$ , we are given a subset of bins $S_{i}\subseteq\mathcal{B}$ . Each ball $i$ is placed into one of the bins in $S_{i}$ uniformly at random.

Proposition 1 ([34, 29]).

For $i\in[b]$ , let $X_{i}$ be the indicator random variable that bin $B_{i}$ is non-empty in the balls-into-bins experiment above, and define $X=\sum_{i=1}^{b}X_{i}$ . Then, for any $0<t\leqslant\operatorname*{{\mathbb{E}}}\left[X\right]$ , we have:

\operatorname*{\textnormal{Pr}}\left(X<\operatorname*{{\mathbb{E}}}\left[X% \right]-t\right)<\exp\left(-\frac{t^{2}}{2\operatorname*{{\mathbb{E}}}\left[X% \right]}\right).

Proof sketch.

For each $i\in[b]$ , let $Y_{i}=1-X_{i}$ and let $N_{i}$ be the random variable denoting the number of balls placed in bin $B_{i}$ . As $(N_{i}:i\in[b])$ has multinomial distribution, the collection $\{N_{i}\}_{i\in[b]}$ is negatively associated (NA) [26, Example 3.1].

Note that $Y_{i}$ is an indicator variable that is equal to $1$ if $N_{i}=0$ and $0$ otherwise. By the properties of NA [26], any non-increasing functions of NA variables is also NA. Therefore, $\{Y_{i}\}_{i\in[q]}$ is NA. Applying the concentration bound for NA variables from [29, Lemma 3b] yields the desired bound. $\hfill\blacktriangleleft$

Concentration Inequality

We use the following standard version of Chernoff bound.

Proposition 2 (Chernoff-Hoeffding bound; cf. [30]).

Let $X_{1},\ldots,X_{n}$ be $n$ independent indicator random variables. Define $X:=\sum_{i=1}^{n}X_{i}$ . For any $\delta\in(0,1)$ , and $\operatorname*{{\mathbb{E}}}\left[X\right]\leqslant\mu$ we have:

\displaystyle\operatorname*{\textnormal{Pr}}\left(X>(1+\delta)\cdot\mu\right)% \leqslant\exp\left(-\frac{\delta^{2}\cdot\mu}{3}\right).

Entropy compression

The following lemma states that we cannot compress random bits efficiently, which forms the key concept behind the entropy compression method. This is a pretty standard result and we provide its elementary proof for completeness.

Lemma 3.

Let $\delta\in(0,1)$ and $f:\{0,1\}^{m}\rightarrow\{0,1\}^{t}$ be any fixed function with the following property: if we sample $x$ uniformly at random from $\{0,1\}^{m}$ , we can recover $x$ from $f(x)$ with probability at least $\delta$ . Then, we should have

t\geqslant m-\log(1/\delta).

Proof.

Let $X\subseteq\{0,1\}^{m}$ be the set of strings that are correctly recovered by $f$ . For any two distinct $x,y\in X$ , it must be that $f(x)\neq f(y)$ ; otherwise, we cannot uniquely recover $x$ from function $f$ . Thus, $f:X\rightarrow\{0,1\}^{t}$ must be injective, which implies that $|X|\leqslant 2^{t}$ .

We also know that $x\in\{0,1\}^{m}$ can be recovered from $f(x)$ with probability at least $\delta$ , therefore $|X|\geqslant\delta\cdot 2^{m}$ . Hence,

2^{t}\geqslant|X|\geqslant\delta\cdot 2^{m},

resulting in the desired $t\geqslant m-\log(1/\delta)$ , concluding the proof. $\hfill\blacktriangleleft$

3 An $O(\Delta^{2}\log{n})$ Update Time Algorithm

We now state our main technical contribution, formalizing Result 2.

Theorem 4 (Formalizing Result 2).

Let $\varepsilon\in(0,1)$ be a fixed constant and $\Delta_{0}$ be sufficiently large as a function of $\varepsilon$ . There is an algorithm that maintains a $(1+\varepsilon)\cdot\Delta/\ln{\Delta}$ coloring of any fully dynamic $n$ -vertex triangle-free graph of maximum degree $\Delta\geqslant\Delta_{0}$ . The algorithm is randomized and with high probability has amortized update time of $O(\Delta^{2}\log{n})$ against adaptive adversaries and $O(\Delta^{2})$ against oblivious adversaries.

We first describe the maintained invariants and the data structures supporting dynamic updates. Next, we introduce an algorithm for maintaining a proper partial coloring of the vertices and analyze its amortized update time, which forms the core technical component of our approach. We then show how this partial coloring can be extended to a full coloring, completing the proof of Theorem 4.

3.1 Setup

Recall that $\Delta$ is a known upper bound on the maximum degree of the graph during the updates. Throughout this section, we fix $\varepsilon>0$ to be any arbitrarily small constant, and use the following two palettes of colors:

\mathcal{C}_{1}:=\left\{1,\cdots,q\right\}\qquad\text{and}\qquad\mathcal{C}_{2% }:=\left\{q+1,\ldots,(1+\varepsilon)\cdot q\right\}\qquad\text{where}\qquad q:% =\frac{(1+\varepsilon)\cdot\Delta}{\ln{\Delta}}.

Here $|\mathcal{C}_{1}|=q$ and $|\mathcal{C}_{2}|=\varepsilon q$ . We aim to use $\mathcal{C}_{1}$ to color most of the vertices and use $\mathcal{C}_{2}$ to complete the coloring through a cleanup algorithm.

For every $v\in V$ , at any time $t$ during the sequence of graphs $(G_{0},G_{1},\cdots,G_{t},\cdots)$ , we define:

$\blacksquare$

$\textnormal{{color}}_{t}(v)$ : the color in $\mathcal{C}_{1}\cup\mathcal{C}_{2}$ assigned to $v$ at time $t$ ; our goal is to keep $\textnormal{{color}}_{t}(\cdot):V\rightarrow\mathcal{C}_{1}\cup\mathcal{C}_{2}$ as a proper coloring of $G_{t}$ .

The main part of the argument is a fully dynamic algorithm PartialColor that maintains a partial coloring $\varphi_{t}:V\rightarrow\mathcal{C}_{1}\cup\left\{\perp\right\}$ with several important properties for us. Specifically, we define, for any vertex $v\in V$ and time $t$ :

$\blacksquare$

$\textnormal{{Avail}}_{t}(v)$ : colors in $\mathcal{C}_{1}$ that are available to $v$ under $\varphi_{t}$ , i.e., have not been assigned to any neighbor of $v$ in $N_{t}(v)$ ; further, set $a_{t}(v):=\left|{\textnormal{{Avail}}_{t}(v)}\right|$ .
$\blacksquare$

$\textnormal{{Free}}_{t}(v)$ : neighbors of $v$ in $N_{t}(v)$ that are free, i.e., have been marked with $\perp$ ; further, set $f_{t}(v):=\left|{\textnormal{{Free}}_{t}(v)}\right|$ .

Lemma 5.

PartialColor maintains a partial coloring $\varphi_{t}:V\rightarrow\mathcal{C}_{1}\cup\left\{\perp\right\}$ after each update at time $t$ such that for all $v\in V$ :

a_{t}(v)\geqslant\Delta^{\varepsilon/2}\qquad\text{and}\qquad f_{t}(v)% \leqslant\frac{\varepsilon q}{2}.

(1)

Moreover, after at least $n$ many updates, the amortized recourse and update time of PartialColor with high probability are, respectively,

$\blacksquare$

$O(\Delta\cdot\log{n})$ and $O(\Delta^{2}\cdot\log{n})$ against adaptive adversary,
$\blacksquare$

$O(\Delta)$ and $O(\Delta^{2})$ against oblivious adversary.

We describe PartialColor in the following subsection and then provide its analysis. We then use Lemma 5 to conclude the proof of Theorem 4.

3.2 The PartialColor Algorithm

PartialColor is a simple local search algorithm: it starts with a graph $G_{t-1}$ that satisfies the constraints of Lemma 5, receives an update $e_{t}=(u_{t},v_{t})$ , and simply tries to “locally fix” any vertex that no longer satisfies the guarantees of Equation 1 by resampling the colors of its neighbors and recursing. Formally, the algorithm is as follows:

Algorithm 1

\textnormal{{PartialColor}}(e_{t})

: Called when

e_{t}=(u_{t},v_{t})

is updated in

G_{t-1}

to obtain

G_{t}

.

1.

Update the data structures $N_{t}(\cdot)$ , $\textnormal{{Avail}}_{t}(\cdot)$ , and $\textnormal{{Free}}_{t}(\cdot)$ for vertices $u_{t},v_{t}$ .
2.

If $e_{t}$ is inserted and $\varphi_{t}(u_{t})=\varphi_{t}(v_{t})$ , set $\varphi_{t}(u_{t})=\perp$ .
3.

while there is $w\in\left\{u_{t},v_{t}\right\}\cup N(u_{t})$ with $a_{t}(w)<\Delta^{\varepsilon/2}$ or $f_{t}(w)>\varepsilon q/2$ , run $\textnormal{{Fix}}(w)$ .

Subroutine $\textnormal{{Fix}}(u)$ :

1.

If $a_{t}(u)<\Delta^{\varepsilon/2}$ , run $\textnormal{{Resample}}(u)$ .
2.

If $f_{t}(u)>\varepsilon q/2$ , then while there is $v\in N_{t}(u)$ with $a_{t}(v)<\Delta^{\varepsilon/2}$ , run $\textnormal{{Fix}}(v)$ .
3.

If $f_{t}(u)>\varepsilon q/2$ still, run $\textnormal{{Resample}}(u)$ .

Subroutine $\textnormal{{Resample}}(u)$ :

1.

For $z\in N(u)$ : resample $\varphi_{t}{(z)}$ uniformly at random from $\textnormal{{Avail}}_{t}(z)\cup\left\{\perp\right\}$ ; update $\textnormal{{Avail}}_{t}(\cdot)$ and $\textnormal{{Free}}_{t}(\cdot)$ for neighbors of $z$ in $N_{t}(z)$ .
2.

While there is $w\in B_{t}(u,2)$ with $a_{t}(w)<\Delta^{\varepsilon/2}$ or $f_{t}(w)>\varepsilon q/2$ , run $\textnormal{{Fix}}(w)$ .

PartialColor aims to eliminate all unsatisfied constraints in Equation 1 by invoking the subroutine Fix on any vertex that violates a constraint. Note that a priori, it is not at all clear that the subroutine Fix would ever terminate even. We will get to that in the main part of the proof. But before that, the following observation shows that each terminating call to Fix strictly reduces the number of unsatisfied constraints.

Observation 6.

For any $u\in V$ , assuming $\textnormal{{Fix}}(u)$ terminates, the partial coloring maintained by the algorithm satisfies both constraints of Equation 1 for $u$ . Moreover, $\textnormal{{Fix}}(u)$ , upon termination, does not break any constraint that was already satisfied.

Proof.

Whenever $u$ does not satisfy a constraint, subroutine $\textnormal{{Fix}}(u)$ , assuming other calls to Fix triggered along the way terminate, triggers a call to $\textnormal{{Resample}}(u)$ . Since $u$ is in its own 2-hop neighbourhood, Resample triggers calls to $\textnormal{{Fix}}(u)$ again. Therefore, the procedure $\textnormal{{Fix}}(u)$ does not exit its while-loops as long as any of the constraints of $u$ remain unsatisfied.

Observe that a call to $\textnormal{{Fix}}(v)$ for any $v\in V$ can generate new violated constraints only when it executes $\textnormal{{Resample}}(v)$ , which changes the colors of vertices in $N_{t}(v)$ . Such color changes can only affect the constraints of vertices in $B_{t}(v,2)$ . However, $\textnormal{{Resample}}(v)$ explicitly invokes $\textnormal{{Fix}}(w)$ for every vertex $w\in B_{t}(v,2)$ whose constraints may have been affected.

Consider an initial call to $\textnormal{{Fix}}(u)$ . Whenever a recoloring causes a constraint violation at some vertex $v$ , the algorithm invokes $\textnormal{{Fix}}(v)$ . Assuming inductively that each invocation of $\textnormal{{Fix}}(v)$ restores all constraints of $v$ before terminating, it follows that all constraint violations caused by the execution of $\textnormal{{Fix}}(u)$ are eventually repaired. Therefore, upon termination of $\textnormal{{Fix}}(u)$ , no previously satisfied constraints will be violated. $\hfill\blacktriangleleft$

To bound the update time of PartialColor we use the entropy compression technique. We argue that the algorithm effectively compresses the random bits used to color the vertices as part of the Resample subroutine. Consequently, if the algorithm runs for too long, it would compress the randomness beyond what is allowed by Lemma 3, leading to a contradiction. The key to this step is the following probabilistic lemma. A similar lemma also appears in [29] (although the second part is entirely different given we use a different “flaw” in the language of [29]).

Lemma 7.

At any point in time in the algorithm:

1.

when calling $\textnormal{{Resample}}(u)$ in Line (1) of $\textnormal{{Fix}}(u)$ :

$\operatorname*{\textnormal{Pr}}\left(a_{t}(u)<\Delta^{\varepsilon/2}\right)% \leqslant 2^{-\frac{\Delta^{\varepsilon/2}}{100}};$
2.

when calling $\textnormal{{Resample}}(u)$ in Line (3) of $\textnormal{{Fix}}(u)$ :

$\operatorname*{\textnormal{Pr}}\left(f_{t}(u)>\frac{\varepsilon q}{2}\right)% \leqslant 2^{-\frac{\varepsilon\cdot\Delta}{50\ln\Delta}}.$

Proof.

We prove each part separately.

Part 1.

The proof is by bounding $\operatorname*{{\mathbb{E}}}\left[a_{t}(u)\right]$ and applying a concentration bound. Recall that a color $c\in\mathcal{C}_{1}$ is available for $u$ at time $t$ iff no neighbor $v\in N_{t}(u)$ samples color $c$ . Since each neighbor $v$ chooses a color uniformly at random from the set $\textnormal{{Avail}}_{t}(v)\cup\{\perp\}$ , the probability that $v$ chooses $c$ is exactly $1/(a_{t}(v)+1)$ if $c\in\textnormal{{Avail}}_{t}(v)$ , and $0$ otherwise. By the independence of these color choices (as $G$ is triangle-free), the probability that $c\in\textnormal{{Avail}}_{t}(u)$ is:

\operatorname*{\textnormal{Pr}}\left(c\in\textnormal{{Avail}}_{t}(u)\right)=% \prod\limits_{\begin{subarray}{c}v\in N_{t}(u)\\ c\in\textnormal{{Avail}}_{t}(v)\end{subarray}}\left(1-\frac{1}{a_{t}(v)+1}% \right).

Therefore, we have

$\displaystyle\operatorname*{{\mathbb{E}}}\left[a_{t}(u)\right]$	$\displaystyle=\sum_{c\in\mathcal{C}_{1}}\prod\limits_{\begin{subarray}{c}v\in N% _{t}(u)\\ c\in\textnormal{{Avail}}_{t}(v)\end{subarray}}\left(1-\frac{1}{a_{t}(v)+1}\right)$
	$\displaystyle\geqslant\sum_{c\in\mathcal{C}_{1}}\prod\limits_{\begin{subarray}% {c}v\in N_{t}(u)\\ c\in\textnormal{{Avail}}_{t}(v)\end{subarray}}\exp\left(-\frac{1}{a_{t}(v)}\right)$	(as $1-1/(x+1)\geqslant e^{-1/x}$ for $x>0$ )
	$\displaystyle=\sum_{c\in\mathcal{C}_{1}}\exp(-\!\sum\limits_{\begin{subarray}{% c}v\in N_{t}(u)\\ c\in\textnormal{{Avail}}_{t}(v)\end{subarray}}\frac{1}{a_{t}(v)})=q\cdot% \operatorname*{{\mathbb{E}}}_{c\sim\mathcal{C}_{1}}\left[e^{-\rho(c)}\right],$

where we define

\rho(c):=\sum\limits_{\begin{subarray}{c}v\in N_{t}(u)\\ c\in\textnormal{{Avail}}_{t}(v)\end{subarray}}\frac{1}{a_{t}(v)}\quad\text{for% each $c\in\mathcal{C}_{1}$}.

We can see that

\displaystyle\operatorname*{{\mathbb{E}}}_{c\sim\mathcal{C}_{1}}\left[\rho(c)% \right]=\sum_{c\in\mathcal{C}_{1}}\frac{1}{q}\cdot\rho(c)=\sum_{c\in\mathcal{C% }_{1}}\frac{1}{q}\cdot\sum\limits_{\begin{subarray}{c}v\in N_{t}(u)\\ c\in\textnormal{{Avail}}_{t}(v)\end{subarray}}\frac{1}{a_{t}(v)}=\frac{1}{q}% \cdot\sum_{v\in N_{t}(u)}\sum_{c\in\textnormal{{Avail}}_{t}(v)}\frac{1}{a_{t}(% v)}\leqslant\frac{\Delta}{q}.

This is because each $v\in N_{t}(u)$ has exactly $a_{t}(v)$ many available colors and $\deg_{t}(u)\leqslant\Delta$ . Therefore, using Jensen’s inequality and convexity of $e^{-x}$ we get

\operatorname*{{\mathbb{E}}}\left[a_{t}(u)\right]\geqslant q\cdot\exp(-% \operatorname*{{\mathbb{E}}}[\rho(c)])\geqslant q\cdot\exp(-\frac{\Delta}{q})=% \frac{(1+\varepsilon)\cdot\Delta}{\ln\Delta}\cdot\exp(-\frac{\ln\Delta}{1+% \varepsilon})\geqslant 2\Delta^{\varepsilon/2},

(2)

where the last inequality is true because $\Delta$ is sufficiently large.

We now prove a concentration bound for $a_{t}(u)$ . The sampling of colors here corresponds to the balls-into-bins framework described in Proposition 1, where the colors in $\mathcal{C}_{1}$ serve as the bins and the neighbors $v\in N_{t}(u)$ act as the balls. Specifically, for each ball $i\in[\deg_{t}(v)]$ , the set of allowed bins $S_{i}$ in the experiment is $\textnormal{{Avail}}_{t}(v_{i})\cup\left\{\perp\right\}$ . Therefore, we can use the same concentration inequality as in Proposition 1 to bound $a_{t}(u)$ . Using Equation 2, we get
$\displaystyle\operatorname*{\textnormal{Pr}}\left(a_{t}(u)<\Delta^{\varepsilon% /2}\right)\leqslant\operatorname*{\textnormal{Pr}}\left(a_{t}(u)<\frac{% \operatorname*{{\mathbb{E}}}\left[a_{t}(u)\right]}{2}\right)\leqslant\exp{(-% \frac{\operatorname*{{\mathbb{E}}}\left[a_{t}(u)\right]}{12})}\leqslant\exp{(-% \frac{\Delta^{\varepsilon/2}}{12})}\leqslant 2^{-\frac{\Delta^{\varepsilon/2}}% {100}},$

concluding the proof of the first part.

Part 2.

For any $v\in N_{t}(u)$ , let $Z_{v}$ be the indicator random variable for $v$ picking $\perp$ . We have

\operatorname*{{\mathbb{E}}}\left[f_{t}(u)\right]=\sum_{v\in N_{t}(u)}% \operatorname*{{\mathbb{E}}}\left[Z_{v}\right]=\sum_{v\in N_{t}(u)}\frac{1}{a_% {t}(v)+1}.

By Observation 6 and since we now consider $\textnormal{{Resample}}(u)$ called in Line (3), we know that $a_{t}(v)\geqslant\Delta^{\varepsilon/2}$ for all $v\in N_{t}(u)$ . Hence, we have,

\displaystyle\operatorname*{{\mathbb{E}}}\left[f_{t}(u)\right]\leqslant\Delta% \cdot\frac{1}{\Delta^{\varepsilon/2}}\ll\frac{\varepsilon q}{4}.

Since the random variables $\{Z_{u}\}_{u\in N_{t}(v)}$ are independent, by Proposition 2, we have

\displaystyle\operatorname*{\textnormal{Pr}}\left(f_{t}(v)\geqslant\varepsilon q% /2\right)

\displaystyle\leqslant\exp(-\frac{\varepsilon q}{12})\leqslant 2^{-\frac{% \varepsilon q}{50}}\leqslant 2^{-\frac{\varepsilon\cdot\Delta}{50\ln\Delta}},

concluding the proof of the second concentration inequality. $\hfill\blacktriangleleft$

We now define a compression scheme for compressing random bits used by the algorithm over a given sequence of updates $(G_{0},G_{1},\ldots,G_{T})$ for some $T\geqslant n$ . In the following, we focus on the case when the updates are done by an adaptive adversary (which is the more interesting case). We will then briefly describe how to handle oblivious adversaries more efficiently.

To continue, we need some definitions. At any point of time during the algorithm, define:

$\blacksquare$

$\textnormal{All}_{t}(v)$ : the set of all possible assignments of colors to neighbors $u$ of $v$ from $\textnormal{{Avail}}_{t}(u)\cup\left\{\perp\right\}$ . This way, we have,

$\left|{\textnormal{All}_{t}(v)}\right|=\prod_{u\in N_{t}(v)}\left(a_{t}(u)+1% \right).$
$\blacksquare$

$\textnormal{Bad}_{t}(v)\subseteq\textnormal{All}_{t}(v)$ : those assignments that will lead to $v$ having $a_{t}(v)<\Delta^{\varepsilon/2}$ or $f_{t}(v)>\varepsilon q/2$ .

(We shall note that the subscript $t$ these definitions is a bit misleading since these sets and parameters can vary many times during processing of a single update; however, to avoid cluttering the notation, we stick with using subscript $t$ here.)

The compression scheme

We maintain a log of the algorithm on $(G_{1},\ldots,G_{T})$ that allows us to reconstruct all random bits used during its execution. At time step $t$ , with update $e_{t}=(u_{t},v_{t})$ , we record the following information:

1.

A single bit indicating the type of update (insertion or deletion), together with $2\log n$ bits specifying the edge $e_{t}$ .
2.

A single bit indicating whether the algorithm terminates at the second line of PartialColor.
3.

If the algorithm reaches Line 3 of PartialColor, for any vertex $w\in N_{t}(u_{t})$ for which $\textnormal{{Fix}}(w)$ was called, we write $O(\log\Delta)$ bits to specify the vertex (we need $\log{\Delta}$ bits instead of $\log{n}$ as we specify this vertex as the $i$ -th neighbor of $u_{t}$ for some $i\in[\Delta]$ ). Additionally, we use $O(1)$ bits to indicate which constraint violation triggered the call to Fix.
4.

For each call to $\textnormal{{Fix}}(u)$ , the input $u$ is specified before this and we have also written down the type of constraint violation. This allows us to know whether $\textnormal{{Fix}}(u)$ terminates in Line (1) or Line (3). If $\textnormal{{Fix}}(u)$ terminates in Line (1), we consider the set $\textnormal{Bad}_{t}(u)$ , namely, the assignment of colors to neighbors of $u$ at this point in time that will result in $u$ having a violated constraint. Since $u$ does have a violated constraint, the assignment of $\varphi_{t}$ to $N_{t}(u)$ in this step belongs to $\textnormal{Bad}_{t}(u)$ . We will write the index $\ell\in\left|{\textnormal{Bad}_{t}(v)}\right|$ to the log to specify this part of $\varphi_{t}$ .

If $\textnormal{{Fix}}(u)$ goes beyond Line (1), we again record each $v\in N_{t}(v)$ that we call $\textnormal{{Fix}}(v)$ on using $O(\log{\Delta})$ bits. Then, we go to Line (3) and if $\textnormal{{Fix}}(u)$ is called here, we write the index $\ell\in\left|{\textnormal{Bad}_{t}(u)}\right|$ corresponding to the assignment of $\varphi_{t}$ to $N_{t}(u)$ at this point (which we know belongs to $\textnormal{Bad}_{t}(u)$ ). Finally, upon completing $\textnormal{{Fix}}(v)$ , we write $O(1)$ bits to mark the end of this subroutine. This process is repeated recursively within each call to Fix.
5.

At the end of all of the updates we also log the final choice of $\varphi_{t}$ in $n\log{\Delta}$ bits.

This concludes the description of our compression scheme. Note that at no point in this process, we explicitly wrote down the random choices made by Resample at the time they were made. Nonetheless, the following observation allows us to argue that we can recover all those random bits from the compression.

Observation 8.

Given the log described above for a sequence of $T$ updates and $S_{T}$ calls to Resample, we can recover all random bits used by Resample in the execution of the algorithm.

Proof.

In the compression scheme, the entire sequence of graphs $G_{1},\ldots,G_{T}$ is recorded explicitly. Moreover, every call to Fix is fully specified in the log by recording the index of the vertex for which Fix is invoked (in a “local” way by starting from $u_{t}$ of the corresponding update at time $t$ , and using the stored $\log{\Delta}$ -bit addresses to go to the specified neighbor and so on), together with the type of constraint violation that triggered the call. As a result, for any call to $\textnormal{{Fix}}(v)$ , we can uniquely reconstruct $v$ and the exact graph on which this call is executed.

We reconstruct the random bits in the reverse order. At time $T$ , the compression explicitly records the final partial coloring $\varphi_{T}$ . The log also specifies the last vertex $v$ whose call to Fix triggered a call to Resample. Since $\textnormal{{Resample}}(v)$ only randomizes the colors of vertices in the neighborhood of $v$ , the coloring $\varphi_{T}$ restricted to this neighborhood uniquely determines the random bits used in this call.

Furthermore, the compression includes an index pointing to the violated constraint that caused this call to Fix. This information allows us to reconstruct the coloring of the neighborhood of $v$ before the call to $\textnormal{{Resample}}(v)$ , as the colors of all vertices outside this neighborhood remain unchanged during this step. Equivalently, from the fixed coloring outside the neighborhood we can reconstruct the set $\textnormal{Bad}(v)$ and hence recover the previous local coloring.

Thus, we recover both the random bits used in the $S$ -th call to Resample and the partial coloring immediately preceding this call. By iterating this argument backwards for the remaining $S-1$ calls, we recover all random bits used by the algorithm. $\hfill\blacktriangleleft$

By Observation 8, we can recover all random bits used by the algorithm on a sequence of updates using the compression scheme above. We now use Lemma 7 to argue that this compression scheme does indeed compress the random bits: roughly speaking, this is because between all possible color assignments to neighborhood of a vertex, most of the resulting colorings do not violate the constraints in Equation 1 by Lemma 7. We formalize and use this in the following lemma to bound the runtime of PartialColor.

Lemma 9.

Let $S_{T}$ be the random variable for the number of times Resample is called after $T$ updates. Against an adaptive adversary, we have:

\displaystyle\operatorname*{\textnormal{Pr}}\left(S_{T}\geqslant T\log{n}+n% \right)\leqslant n^{-T},

and against an oblivious adversary we have

\displaystyle\operatorname*{\textnormal{Pr}}\left(S_{T}\geqslant T+n\right)% \leqslant\Delta^{-T}.

(note that the main difference between the two equations are in $T\log{n}$ and $T$ terms and the RHS).

Proof.

We first prove the inequality against an adaptive adversary. Define

g(n,T):=T\log{n}+n.

Suppose, for the sake of contradiction, that there exists $T\geqslant n$ and an adaptive adversary oracle $\mathcal{O}_{A}$ that can force PartialColor to have $\operatorname*{\textnormal{Pr}}\left(S_{T}\geqslant g(n,T)\right)>n^{-T}$ .

Using the oracle $\mathcal{O}_{A}$ to generate the update sequence, we execute PartialColor and obtain a string $R_{T}$ consisting of all random bits used by the algorithm up to the step where the number of calls to Resample reaches $S_{T}=g(n,T)$ , at which point we halt. We also run the compression scheme above (with some minor modifications) as described below.

Let $v_{i}$ be the vertex triggering the $i$ -th call to Resample at time $t_{i}$ . Define

\mathcal{W}_{i}:=\left|{\textnormal{All}_{t_{i}}(v)}\right|,

representing the number of possible colorings for the neighborhood of $v_{i}$ . Each call to Resample picks an integer from $[\mathcal{W}_{i}]$ uniformly, requiring $\log\mathcal{W}_{i}$ random bits. Note that $\log\mathcal{W}_{i}\leqslant\Delta\log{\Delta}$ since every vertex has at most $\Delta$ neighbors and less than $\Delta$ available colors. To normalize the bit-count, let $\ell_{i}:=\Delta\log\Delta-\log\mathcal{W}_{i}$ . By generating $\ell_{i}$ additional random bits, each call uses exactly $\Delta\log\Delta$ bits. We consider these extra bits as the randomness of the algorithm also. This way, the total number of bits generated by the algorithm is:

|R_{T}|=\sum_{i=1}^{g(n,T)}\log\mathcal{W}_{i}+\ell_{i}=g(n,T)\cdot\Delta\log\Delta.

We now describe the compression. We basically do exactly as the compression scheme described earlier except that the extra $\sum\ell_{i}$ bits are recorded without any changes. Recall that $\textnormal{Bad}_{t_{i}}(v_{i})$ is the set of “bad” colorings for the neighborhood of $v_{i}$ , which cause a constraint violation on this vertex. By Lemma 7, regardless of which lines of Fix is used to call Resample,

|\textnormal{Bad}_{t_{i}}(v_{i})|\leqslant\max\left(2^{-\frac{\Delta^{% \varepsilon/2}}{100}}\nobreak\ ,\nobreak\ 2^{-\frac{\varepsilon\Delta}{50\ln% \Delta}}\right)\cdot|\textnormal{All}_{t_{i}}(v_{i})|\leqslant 2^{-\frac{% \Delta^{\varepsilon/2}}{100}}\cdot\mathcal{W}_{i};

the last inequality is true as $\Delta$ is sufficiently large. The compression scheme logs

\log|\textnormal{Bad}_{t_{i}}(v_{i})|+\ell_{i}+O(1)

bits per call to Resample (ignoring the recursive calls inside Resample). Summing over all calls to Resample, the length of the log written for these parts is:

$\displaystyle\sum_{i=1}^{g(n,T)}\log\|\textnormal{Bad}_{t_{i}}(v_{i})\|+\ell_{i}% +O(1)$	$\displaystyle\leqslant\sum_{i=1}^{g(n,T)}\left(\log{\mathcal{W}_{i}}-\frac{% \Delta^{\varepsilon/2}}{100}+\ell_{i}+O(1)\right)$	(by the equation above)
	$\displaystyle=\left(\sum_{i=1}^{g(n,T)}\log{\mathcal{W}_{i}}+\ell_{i}+O(1)% \right)-g(n,T)\cdot\frac{\Delta^{\varepsilon/2}}{100}$
	$\displaystyle=g(n,T)\cdot\Delta\log\Delta+g(n,T)\cdot O(1)-g(n,T)\cdot\frac{% \Delta^{\varepsilon/2}}{100}.$	(as $\log\mathcal{W}_{i}+\ell_{i}=\Delta\log\Delta$ )

The calculations above point to the exact step wherein we are “compressing” the randomness.

Finally, note that the compression scheme also stores $O(\log{\Delta})$ bits per call to Fix and since the number of calls to Fix and Resample are asymptotically the same, the log also contains $O(g(n,T)\cdot\log{\Delta})$ many bits for handling the calls to Fix. Denoting $L_{T}$ as the log generated by this compression scheme (and the modifications mentioned above), we have,

$\displaystyle\left\|{L_{T}}\right\|$	$\displaystyle\leqslant T\cdot(2\log{n}+2)$	(for logging the updates, their type, and if they continue to Line 3 of PartialColor)
	$\displaystyle+g(n,T)\cdot\Delta\log\Delta+g(n,T)\cdot O(\log{\Delta})-g(n,T)% \cdot\frac{\Delta^{\varepsilon/2}}{100}$	(for logging the calls to Resample and Fix)
	$\displaystyle+n\log{\Delta}.$	(to log the partial coloring upon halting the scheme after $S_{T}=g(n,T)$ )

Consider the following scenario. We sample $x\in\left\{0,1\right\}^{a}$ for $a=g(n,T)\Delta\log{\Delta}$ uniformly at random and use it to generate all the randomness $R_{T}$ in the above process. If the process fails because $S_{T}<g(n,T)$ , we let $f(x)$ writes “fail” in $O(1)$ bits and otherwise, if $S_{T}=g(n,T)$ , it will write “success” plus the log $L_{T}$ specified above. Thus, by our earlier (contradicting) assumption, we will generate $L_{T}$ with probability at least $n^{-T}$ , from which, by Observation 8, we can correctly recover $x$ . Thus, by Lemma 3, we should have

\left|{L_{T}}\right|+O(1)\geqslant\left|{R_{T}}\right|-\log{(n^{T})}.

Plugging in the bounds we have for the lengths of $L_{T}$ and $R_{T}$ above, gives us
$T\cdot(2\log{n}+2)+g(n,T)\cdot\Delta\log\Delta+g(n,T)\cdot O(\log{\Delta})-g(n% ,T)\cdot\frac{\Delta^{\varepsilon/2}}{100}+n\log{\Delta}\geqslant g(n,T)\cdot% \Delta\log{\Delta}-T\log{n},$

which implies that (since $\Delta^{\varepsilon/2}\gg\log{\Delta}$ for large enough $\Delta$ as a function of $\varepsilon$ ),

g(n,T)\leqslant\frac{200}{\Delta^{\varepsilon/2}}\cdot\left(4T\log{n}+n\log{% \Delta}\right)<T\log{n}+n,

contradicting our definition of $g(n,T)$ . Thus, we have

\operatorname*{\textnormal{Pr}}\left(S_{T}>T\log{n}+n\right)\leqslant n^{-T},

completing the proof for adaptive adversaries.

Improved bounds for oblivious adversaries

For oblivious adversaries, the only difference is that we do not need to explicitly write down the $T$ updates in our log, since an oblivious adversary behaves independent of the input. Define

h(n,T)=T+n,

and now suppose towards a contradiction that there exists a sequence of $T$ updates $e_{1},\ldots,e_{T}$ such that running PartialColor on the graphs $G_{0},\ldots,G_{T}$ leads to

\operatorname*{\textnormal{Pr}}\left(S_{T}\geqslant h(n,T)\right)\geqslant% \Delta^{-T}.

If no such fixed sequence exists, then the bound in the lemma statement immediately holds. We now show the above equation will lead to a contradiction.

We again run the same exact compression scheme but now only spend $O(T)$ bits for updates just to write down whether or not PartialColor reached its Line 3, without specifying the updates since they are globally fixed. Using the same exact argument as before, this allows us to summarize our random bits $R_{T}$ of length $h(n,T)\Delta\log{\Delta}$ , with probability at least $\Delta^{-T}$ , into a recoverable log $L_{T}$ of length

\left|{L_{T}}\right|=O(T)+h(n,T)\cdot\Delta\log{\Delta}+h(n,T)\cdot O(\log{% \Delta})-h(n,T)\cdot\frac{\Delta^{\varepsilon/2}}{100}+n\log{\Delta}.

Thus, by using Lemma 3 as before, we have $\left|{L_{T}}\right|\geqslant\left|{R_{T}}\right|-T\log{\Delta}$ , implying that

h(n,T)\leqslant\frac{200}{\Delta^{\varepsilon/2}}\cdot\left(T\log{\Delta}+n% \log{\Delta}\right)<T+n,

contradicting with the choice of $h(n,T)$ , and concluding the proof. $\hfill\blacktriangleleft$

We are now ready to conclude the proof of Lemma 5.

Proof of Lemma 5.

The algorithm PartialColor always produces a proper partial coloring. This is because (1) if after an update $(u,v)$ , if $\varphi_{t}(u)=\varphi_{t}(v)$ and neither are $\perp$ , we will make one of them $\perp$ , and (2) the call $\textnormal{{Resample}}(v)$ recolors the vertices in $N_{t}(v)$ and since the graph is triangle-free, $N_{t}(v)$ is an independent set, and thus each vertex $u\in N_{t}(v)$ can independently choose a color uniformly at random from $\textnormal{{Avail}}_{t}(u)\ \cup\left\{\perp\right\}$ without creating a monochromatic edge. Consequently, the resulting coloring remains proper.

By induction, suppose $G_{t-1}$ satisfies the properties stated in Lemma 5. Our goal is to show that after processing time step $t$ , the algorithm PartialColor restores all constraints. The only difference between $G_{t}$ and $G_{t-1}$ arises from the edge $e_{t}$ . If the corresponding constraints are violated, the subroutine Fix is invoked. By Observation 6, all violated constraints are resolved by the call to Fix, and no new violations are introduced. Therefore, after running PartialColor, for all $v\in V$ we have

a_{t}(v)\geqslant\Delta^{\varepsilon/2}\qquad\text{and}\qquad f_{t}(v)% \leqslant\frac{\varepsilon q}{2}.

For any $T\geqslant n$ , when facing an adaptive adversary, by Lemma 9 we know that with probability at least $1-n^{-T}$ , the subroutine Resample is invoked at most $O(T\log{n})$ time. Each call to $\textnormal{{Resample}}(v)$ takes $O(\Delta^{2})$ times (for sampling colors for $O(\Delta)$ vertices and going over $B_{t}(v,2)$ of size $\Delta^{2}$ ) and each call to $\textnormal{{Fix}}(v)$ takes $O(\Delta)$ time (to go over all neighbors of $v$ in Line 2 if needed). Since the number of calls to Resample and Fix is asymptotically the same, the total runtime of the algorithm after $T$ updates is $O(T\cdot\Delta^{2}\log{n})$ with probability $1-n^{-T}$ . In other words, the amortized update time of the algorithm is $O(\Delta^{2}\log{n})$ with probability at least $1-n^{-T}$ . Taking union bound for $T$ from $n$ to infinity, we have,

\operatorname*{\textnormal{Pr}}\left(\text{amortized update time is ever more % than $O(\Delta^{2}\log{n})$}\right)\leqslant\sum_{T=n}^{\infty}n^{-T}=O(n^{-n}),

namely, with (super exponentially) high probability, the amortized update time for any sequence of updates of length at least $n$ is $O(\Delta^{2}\log{n})$ . The bound for the recourse can also be proven similarly to be $O(\Delta\log{n})$ since each call to $\textnormal{{Resample}}(v)$ has a recourse of $O(\Delta)$ at most.

Finally, switching to oblivious adversaries, using the improved bounds of Lemma 9, the same argument instead gives us

\operatorname*{\textnormal{Pr}}\left(\text{amortized update time is ever more % than $O(\Delta^{2})$}\right)\leqslant\sum_{T=n}^{\infty}\Delta^{-T}=O(\Delta^{% -n}),

which again implies the desired bounds with (exponentially) high probability. $\hfill\blacktriangleleft$

3.3 Concluding the Proof of Theorem 4

We are now ready to conclude the proof of Theorem 4. For this, we present the following algorithm. Upon each update, we first invoke PartialColor to resolve any conflicts among vertices colored from $\mathcal{C}_{1}$ . Then, any vertex that remains uncolored is assigned a color from $\mathcal{C}_{2}$ using a simple greedy procedure. Note that

|\mathcal{C}_{1}\cup\mathcal{C}_{2}|=(1+2\varepsilon)\cdot\frac{\Delta}{\ln% \Delta}.

By initially replacing $\varepsilon$ with $\varepsilon/2$ , this yields a $(1+\varepsilon)\Delta/\ln\Delta$ coloring.

Algorithm 2 Called when

e_{t}=(u_{t},v_{t})

is updated in

G_{t-1}

to obtain

G_{t}

.

1.

Call $\textnormal{{PartialColor}}(e_{t})$ and store all vertices whose color changes in a set $L$ .
2.

For each $v\in L$ with $\varphi_{t}(v)=\perp$ , assign $v$ an available color by checking the neighborhood of $v$ and finding a color in $\mathcal{C}_{2}$ not assigned to any of its neighbors.

It is worth noting that when running PartialColor, any vertex $u$ that previously received a color from $\mathcal{C}_{2}$ can be treated as having color $\perp$ (this way, the coloring $\varphi_{t}$ of PartialColor does not look at colors of vertices in $\mathcal{C}_{2}$ , nor any vertex colored from $\mathcal{C}_{2}$ in Line 2 of Algorithm 2 ever changes $\varphi_{t}$ ). We now use Algorithm 2 to prove Theorem 4.

Proof of Theorem 4.

At each update step $t$ , the subroutine PartialColor maintains a proper partial coloring using the color set $\mathcal{C}_{1}$ , and for every vertex $v$ we have $f_{t}(v)\leqslant\frac{\varepsilon q}{2}$ . Since $|\mathcal{C}_{2}|=\varepsilon q$ , there are sufficiently many available colors to greedily color all remaining uncolored vertices using $\mathcal{C}_{2}$ in the second phase of Algorithm 2. So Algorithm 2 maintains a proper $(1+\varepsilon)\frac{\Delta}{\ln\Delta}$ coloring (after rescaling $\varepsilon\leftarrow\varepsilon/2$ ).

The runtime of the first step of Algorithm 2 is exactly the same as that of PartialColor. For the second step, the runtime is $O(\Delta)$ time per vertex in $L$ . Recall that vertices in $L$ are the ones whose color changed by PartialColor in this step and thus are bounded by the recourse of PartialColor. This implies that the amortized update time of the algorithm, against an adaptive adversary, is $O(\Delta^{2}\log{n})+O(\Delta\log{n})\cdot O(\Delta)=O(\Delta^{2}\log{n})$ , with high probability by Lemma 5. The bound of $O(\Delta^{2})$ on the amortized update time follows exactly the same using the improved bound of Lemma 5 for oblivious adversaries. $\hfill\blacktriangleleft$

4 A $\Delta^{o(1)}\log{n}$ Update Time Algorithm

We now present our final algorithm for maintaining an $O(\Delta/\ln\Delta)$ coloring of triangle-free graphs with $\Delta^{o(1)}\log{n}$ amortized update time. The following theorem formalizes Result 1.

Theorem 10 (Formalizing Result 1).

For any fixed $\gamma\in(0,1)$ , there exists an integer $K=O(1/\gamma^{2})$ such that the following holds. There is a randomized algorithm that with high probability maintains a $\left(K\cdot{\Delta}/{\ln\Delta}\right)$ coloring of any triangle-free fully dynamic graph with maximum degree $\Delta$ with amortized update time of $O(\Delta^{\gamma}\cdot\log{n})$ against an adaptive adversary and $O(\Delta^{\gamma})$ against an oblivious adversary.

To prove this theorem, we design a family of recursive algorithms $\{\mathbb{A}_{k}\}_{k=1}^{\infty}$ with progressively better update times. The base case of this family, $\mathbb{A}_{1}$ , is Algorithm 2 which has update time $\approx\Delta^{2}$ . For larger values of $k>1$ , $\mathbb{A}_{k}$ achieves $\approx\Delta^{O(1/k)}$ amortized update time.

Lemma 11.

For any integer $k\geqslant 1$ , there is a randomized algorithm that with high probability maintains an $O(k^{2}\cdot{\Delta}/{\ln{\Delta}})$ coloring of any fully dynamic $n$ -vertex triangle-free graph of maximum degree $\Delta$ with amortized update time:

$\blacksquare$

$O\left(k!\cdot\Delta^{\frac{2}{2k-1}}\cdot\log{n}\right)$ against an adaptive adversary; and,
$\blacksquare$

$O\left(k!\cdot\Delta^{\frac{2}{2k-1}}\right)$ against an oblivious adversary.

Theorem 10 follows from Lemma 11 immediately by setting $k=\Theta(1/\gamma)$ and $K=O(k^{2})$ (and noting that $\gamma$ is fixed independent of $n$ and thus the $k!$ term in the update time is suppressed in the asymptotic notation.) Note that in the limit, one can set $k$ as large as some $k=o(\sqrt{\log{\Delta}})$ to maintain an $o(\Delta)$ coloring of triangle-free graphs in ${\Delta^{\Theta(\frac{\log\log{\Delta}}{\sqrt{\log{\Delta}}})}\log{n}}$ amortized update time. We prove Lemma 11 in the rest of this section.

For any integer $k\geqslant 1$ , algorithm $\mathbb{A}_{k}$ receives an upper bound $\Delta$ on the maximum degree of the graph it will ever encounter, and the palette $\mathcal{C}$ of the available colors in the initialization phase. Then, during the update phase, $\mathbb{A}_{k}$ receives updates of the form $(u,v,\pm)$ , for $u,v\in V$ , which corresponds to inserting or deleting the edge $(u,v)$ from the underlying graph.

The algorithm $\mathbb{A}_{1}$ is our algorithm in Theorem 4. We now describe $\mathbb{A}_{k}$ for any $k>1$ on an input dynamic graph $G$ on vertices $V$ with maximum degree $\Delta$ . Define the following two parameters

\displaystyle b_{k}=b_{k}(\Delta):=\frac{1}{2}\cdot\Delta^{\frac{2}{2k-1}}% \qquad\text{and}\qquad c_{k}=c_{k}(\Delta):=(k+1)\cdot(2k-1)\cdot\frac{\Delta}% {\ln\Delta}.

(3)

We require the palette $\mathcal{C}$ of available colors to $\mathbb{A}_{k}$ to be of size $c_{k}$ . This palette is further partitioned arbitrarily into $b_{k}$ sets $\mathcal{C}_{1},\cdots,\mathcal{C}_{b_{k}}$ of equal size.

For every vertex $v\in V$ , the algorithm maintains the following data structures that is updated in each time step:

$\blacksquare$

A partition of the vertex set into $b_{k}$ sets $V_{1},\ldots,V_{b_{k}}$ . For every vertex $v\in V$ , we use $p(v)\in[b_{k}]$ to denote the index of the partition it belongs to. Initially, vertices are partitioned arbitrarily.
$\blacksquare$

$\textnormal{indeg}(v)$ : the degree of $v$ in the induced subgraph of $G$ on $V_{p(v)}$ , namely, the partition $v$ belongs to. We refer to $\textnormal{indeg}(v)$ as the induced degree of $v$ .
$\blacksquare$

$N(v,i)$ : the neighbors of $v$ inside the induced subgraph on $V_{i}$ , denoted by $G[V_{i}]$ .

The goal of the algorithm is to color vertices in each set $V_{i}$ using only the colors in $\mathcal{C}_{i}$ . To ensure possibility of this, we maintain an invariant on the maximum degree of each $G[V_{i}]$ for $i\in[b_{k}]$ .

Invariant 11.

For any vertex $v\in V$ , $\textnormal{indeg}(v)\leqslant\left(1+\frac{1}{k}\right)\cdot\frac{\Delta}{b_{% k}}$ .

Equipped with Section 4, the algorithm $\mathbb{A}_{k}$ runs $b_{k}$ copies of the algorithm $\mathbb{A}_{k-1}$ , one on each subgraph $G[V_{i}]$ and color palette $\mathcal{C}_{i}$ for $i\in[b_{k}]$ with an upper bound of $\Delta(G[V_{i}])\leqslant(1+1/k)\Delta/b_{k}$ on the maximum degree of the subgraph. Since the palettes $\mathcal{C}_{i}$ ’s are disjoint, this will lead to a proper coloring of the entire graph. We can now formalize the algorithm.

Algorithm 3 [Algorithm

\mathbb{A}_{k}

of Lemma 11]

1.

Initialization phase: Initialize $b_{k}$ copies of $\mathbb{A}_{k-1}$ , where the $i$ -th copy, denoted by $\mathbb{A}_{k-1}[i]$ is given the palette $\mathcal{C}_{i}$ and the promised upper bound on maximum degree $(1+1/k)\Delta/b_{k}$ . During the updates, $\mathbb{A}_{k-1}[i]$ will be given the dynamic graph $G_{i}=(V,E[V_{i}])$ , the graph with vertices $V$ , but only edges that are between vertices of the set $V_{i}$ of the partition⁴⁴4Setting vertices of $G_{i}$ to be $V$ instead of $V_{i}$ is simply to bypass having to define operations for inserting or deleting vertices in addition to edges..
2.
Update phase: Given an update $(u_{t},v_{t},\pm)$ to $G$ at time $t$ :
1. (a)
  
  Update $N(u_{t},p(v_{t})),N(v_{t},p(u_{t}))$ and $\textnormal{indeg}(u_{t}),\textnormal{indeg}(v_{t})$ accordingly.
2. (b)
  
  If Section 4 no longer holds, run the subroutine FixInvariant.
3. (c)
  
  Once Section 4 continues to hold, if $p(u_{t})\neq p(v_{t})$ , terminate, otherwise pass the update $(u_{t},v_{t},\pm)$ to $\mathbb{A}_{k-1}[i]$ , where $i=p(u_{t})=p(v_{t})$ , to update the colors.

Subroutine FixInvariant:

1.

Let $w$ be any vertex violating the invariant and let $i=p(w)$ .
2.

Remove all edges of $w$ in $G_{i}$ (i.e., inside $E[V_{i}]$ ) by calling $\mathbb{A}_{k-1}[i]$ for each edge.
3.

Find an index $j\in[b_{k+1}]$ such that $\left|{N(w,j)}\right|\leqslant\Delta/b_{k}$ (such an index exist by pigeonhole principle). Remove $w$ from $V_{i}$ and insert it to $V_{j}$ and update $p(w)$ .
4.

Insert all edges of $w$ incident on $E[V_{j}]$ to the graph $G_{j}$ by calling $\mathbb{A}_{k-1}[j]$ for each edge.
5.

If Section 4 still does not hold, call FixInvariant again.

We use a simple potential function argument to argue that the number of calls to FixInvariant (including recursive calls inside it) across a fixed number of updates will be bounded. We will use this later both in the proof of the correctness of the algorithm and to bound its runtime.

Lemma 12.

Starting from an empty graph $G$ as input to $\mathbb{A}_{k}$ , over any sequence of $T$ updates (even by an adaptive adversary), the total number of times FixInvariant is called is $O(T\cdot k\cdot b_{k}/\Delta)$ .

Proof.

Define the potential function:

\Phi:=\sum_{v\in V}\textnormal{indeg}(v).

Each update can increase $\Phi$ by at most two. On the other hand, whenever FixInvariant is called, one vertex $w$ with $\textnormal{indeg}(w)>(1+1/k)\cdot\Delta/b_{k}$ moves from some set $V_{i}$ to another $V_{j}$ resulting in $\textnormal{indeg}(w)\leqslant\Delta/b_{k}$ . Removal of $w$ from $V_{i}$ reduces $\textnormal{indeg}(w)$ and induced degrees of neighbors in $V_{i}$ by at least $2(1+1/k)\Delta/b_{k}$ in total. On the other hand, including $w$ in $V_{j}$ increases the induced degrees of vertices by at most $2\Delta/b_{k}$ . As such, this move reduces $\Phi$ by at least $2/k\cdot\Delta/b_{k}$ .

Thus, over a sequence of $T$ updates, we increase $\Phi$ to at most $2T$ and $\Phi$ can never become negative, thus there can be at most

\frac{2T}{2/k\cdot\Delta/b_{k}}=\frac{T\cdot k\cdot b_{k}}{\Delta},

many calls to FixInvariant, as desired. $\hfill\blacktriangleleft$

Lemma 12 ensures that the subroutine FixInvariant terminates in $\mathbb{A}_{k}$ and thus we can safely assume Section 4 when running the algorithm. Using this, we can prove the correctness of the algorithm. Before that, we should note while the implementation of $\mathbb{A}_{k}$ for $k>1$ in Algorithm 3 is deterministic, the base case algorithm, namely, $\mathbb{A}_{1}$ from Theorem 4, is a randomized algorithm. Thus, each of $\mathbb{A}_{k}$ is also a randomized algorithm.

Lemma 13.

With high probability, $\mathbb{A}_{k}$ computes a proper coloring of the input graph with $c_{k}$ colors.

Proof.

Firstly, consider the dynamic graph $G_{i}=(V,E[V_{i}])$ defined throughout the updates. This graph is updated through direct adversary updates to $G$ plus updates done in FixInvariant. Here we should note that to accurately implement FixInvariant, we should technically first collect all insertion and deletion of edges decided across all calls of FixInvariant inside a single original update to the graph, and then, once FixInvariant is entirely finished do all the insertions and deletions at the end. This way, (1) all updates to the dynamic graph $G_{i}$ are passed to it via $\mathbb{A}_{k-1}[i]$ , and (2) we can assume an upper bound of $(1+1/k)\Delta/b_{k}$ on the maximum degree of graph $G_{i}$ . This means all calls to $\mathbb{A}_{k-1}[i]$ for $i\in[b_{k}]$ are valid throughout the execution of $\mathbb{A}_{k}$ .

We know that Section 4 holds and for any $i\in[k]$ , $\mathbb{A}_{k-1}[i]$ is run entirely on the dynamic graph $G_{i}=(V,E[V_{i}])$ with maximum degree $(1+1/k)\Delta/b_{k}$ . By Equation 3, this means that $\mathbb{A}_{k-1}[i]$ requires a palette of size

$\displaystyle c_{k-1}(\frac{(1+1/k)\cdot\Delta}{b_{k}})$	$\displaystyle=k\cdot(2k-3)\cdot\frac{(1+1/k)\cdot\Delta}{b_{k}\cdot\ln{((1+1/k% )\cdot\Delta/b_{k})}}$	(by Equation 3 for $c_{k-1}$ )
	$\displaystyle=(k+1)\cdot(2k-3)\cdot\frac{\Delta}{b_{k}\cdot\ln{(2\cdot(1+1/k)% \cdot\Delta^{\frac{2k-3}{2k-1}}})}$	(by Equation 3 for $b_{k}$ )
	$\displaystyle\leqslant(k+1)\cdot(2k-3)\cdot\frac{2k-1}{2k-3}\cdot\frac{\Delta}% {b_{k}\cdot\ln{\Delta}}$
	$\displaystyle=\frac{c_{k}}{b_{k}}.$	(by Equation 3 for $c_{k}$ )

This is precisely the size of the palette $\mathcal{C}_{i}$ provided to $\mathbb{A}_{k-1}[i]$ . Thus, as long as $\mathbb{A}_{k-1}[i]$ , for each $i\in[b_{k}]$ , works correctly, so does $\mathbb{A}_{k}$ . Finally, since $V_{1},\ldots,V_{b_{k}}$ is a partition of $V$ and we are using disjoint palettes for each $V_{i}$ , the union of colorings found by $\mathbb{A}_{k-1}[i]$ ’s is also a proper coloring of the entire graph. This concludes the proof. $\hfill\blacktriangleleft$

Finally, we can analyze the update time of the algorithm. In the following, we focus on adaptive adversaries first and then point out how to improve the runtime for oblivious adversaries. For any $k\geqslant 1$ , define:

$T_{k}(\Delta):$ a high probability upper bound on the amortized update time of $\mathbb{A}_{k}$

on a graph of maximum degree $\Delta$ against an adaptive adversary.

We prove the following upper bound on $T_{k}(\cdot)$ .

Lemma 14.

For any $k\geqslant 1$ ,

T_{k}(\Delta)=O(k!\cdot\Delta^{\frac{2}{2k-1}}\cdot\log{n}).

Proof.

By Theorem 4, for $\mathbb{A}_{1}$ , we have

T_{1}(\Delta)=O(\Delta^{2}\log{n}),

which fits the desired bounds for $k=1$ . This establishes the base case. We now prove the bounds for any $k>1$ by analyzing Algorithm 3.

The amortized update time of Algorithm 3, ignoring the time to call FixInvariant for now, is $O(1)$ for updating the data structures, plus running one copy of $\mathbb{A}_{k-1}$ on a graph of maximum degree $O(\Delta/b_{k})$ . By induction, and the choice of $b_{k}$ in Equation 3, this takes

T_{k-1}\left(O(\frac{\Delta}{b_{k}})\right)=T_{k-1}\left(O(\Delta^{\frac{2k-3}% {2k-1}})\right)=O((k-1)!\cdot\Delta^{\frac{2}{2k-1}}\cdot\log{n}).

We now bound the runtime of the calls to FixInvariant. Firstly, in each call, it takes $O(\Delta)$ time to move the considered vertex $w$ from one set $V_{i}$ to another set $V_{j}$ . Moreover, it takes another $O(\Delta/b_{k})$ many calls to $\mathbb{A}_{k-1}$ to remove and insert edges of $w$ . Finally, to implement FixInvariant efficiently, we can keep a list of vertices whose degree have changed in each call to FixInvariant (when we update the edge incident on that vertex) so that we can find a vertex $w$ that violates Section 4 (if any) in $O(1)$ time without having to search the entire graph.

Thus, a single call to FixInvariant takes

O(\Delta)+O(\Delta/b_{k})\cdot T_{k-1}\left(O(\frac{\Delta}{b_{k}})\right)

time in total. Moreover, by Lemma 12, over a sequence of $T$ updates, the total number of calls to FixInvariant is $O(k\cdot T\cdot b_{k}/\Delta)$ . Thus, the amortized update time of this step will be

	$\displaystyle O(k\cdot b_{k})+O(k)\cdot T_{k-1}\left(O(\frac{\Delta}{b_{k}})\right)$	$\displaystyle=O(k\cdot\Delta^{\frac{2}{2k-1}})+O(k)\cdot O((k-1)!\cdot\Delta^{% \frac{2}{2k-1}}\cdot\log{n})$
		$\displaystyle=O(k!\cdot\Delta^{\frac{2}{2k-1}}\cdot\log{n}),$

concluding the proof. $\hfill\blacktriangleleft$

Lemmas 13 and 14 together conclude the proof of Lemma 11 for the adaptive strategies. We should note that since over a sequence of $T$ updates, we are running $T\cdot\mbox{\rm poly}(n)$ many copies of $\mathbb{A}_{1}$ whereas error probability of $\mathbb{A}_{1}$ is only $n^{-T}$ , we can do a union bound over all probabilistic guarantees required in our proof.

Finally, to prove Lemma 11 for oblivious adversaries, notice that by Theorem 4, against an oblivious adversary, $\mathbb{A}_{1}$ has an amortized update time of $O(\Delta^{2})$ instead. Thus, the same proof of Lemma 14, with the base case of $O(\Delta^{2}\log{n})$ switched with $O(\Delta^{2})$ , implies that the amortized update time of $\mathbb{A}_{k}$ has no dependence on $\log{n}$ and is $O(k!\cdot\Delta^{\frac{2}{2k-1}})$ time instead.

This fully concludes the proof of Lemma 11 and by extension Theorem 10.

References

[1] Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. Beyond the lovász local lemma: Point to set correlations and their algorithmic applications. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 725–744. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00049.
[2] Noga Alon and Sepehr Assadi. Palette sparsification beyond ( $\Delta$ +1) vertex coloring. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, Virtual Conference, August 17-19, 2020, volume 176 of LIPIcs, pages 6:1–6:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.6.
[3] Noga Alon, Michael Krivelevich, and Benny Sudakov. Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Series B, 77(1):73–82, 1999. doi:10.1006/JCTB.1999.1910.
[4] Nikhil Bansal, Anupam Gupta, and Guru Guruganesh. On the lovász theta function for independent sets in sparse graphs. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 193–200. ACM, 2015. doi:10.1145/2746539.2746607.
[5] Soheil Behnezhad, Rajmohan Rajaraman, and Omer Wasim. Fully dynamic $(\Delta+1)$ -coloring against adaptive adversaries. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4983–5026. SIAM, 2025. doi:10.1137/1.9781611978322.169.
[6] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1671–1684. ACM, 2022. doi:10.1145/3519935.3520064.
[7] Anton Bernshteyn. The johansson-molloy theorem for dp-coloring. Random Structures & Algorithms, 54(4):653–664, 2019. doi:10.1002/RSA.20811.
[8] Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Deterministic dynamic maximal matching in sublinear update time. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 132–143. ACM, 2025. doi:10.1145/3717823.3718153.
[9] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022, LIPIcs, pages 20:1–20:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.20.
[10] Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1–20. SIAM, 2018. doi:10.1137/1.9781611975031.1.
[11] Sayan Bhattacharya, Martín Costa, Nadav Panski, and Shay Solomon. Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 3393–3440. SIAM, 2024. doi:10.1137/1.9781611977912.122.
[12] Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, and Shay Solomon. Fully dynamic $(\Delta+1)$ -coloring in $O(1)$ update time. ACM Trans. Algorithms, 18(2):10:1–10:25, 2022. doi:10.1145/3494539.
[13] Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022, LIPIcs, pages 17:1–17:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.17.
[14] Marthe Bonamy, Tom Kelly, Peter Nelson, and Luke Postle. Bounding $\chi$ by a fraction of $\Delta$ for graphs without large cliques. Journal of Combinatorial Theory, Series B, 157:263–282, 2022. doi:10.1016/J.JCTB.2022.06.002.
[15] Rowland Leonard Brooks. On colouring the nodes of a network. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 37(2), pages 194–197. Cambridge University Press, 1941.
[16] Aleksander B. G. Christiansen and Eva Rotenberg. Fully-dynamic $\alpha+2$ arboricity decompositions and implicit colouring. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022, volume 229 of LIPIcs, pages 42:1–42:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.42.
[17] Aleksander B. G. Christiansen, Eva Rotenberg, and Juliette Vlieghe. Sparsity-parameterised dynamic edge colouring. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024, Helsinki, Finland, June 12-14, 2024, volume 294 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SWAT.2024.20.
[18] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1201–1214. ACM, 2023. doi:10.1145/3564246.3585111.
[19] Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1937–1945. SIAM, 2019. doi:10.1137/1.9781611975482.117.
[20] Maxime Flin and Magnús M. Halldórsson. Faster dynamic $(\Delta+1)$ -coloring against adaptive adversaries. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, volume 334 of LIPIcs, pages 79:1–79:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.79.
[21] David A. Grable and Alessandro Panconesi. Fast distributed algorithms for {Brooks-Vizing} colourings. In Howard J. Karloff, editor, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA, pages 473–480. ACM/SIAM, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314829.
[22] Bernhard Haeupler, Slobodan Mitrovic, Srikkanth Ramachandran, Wen-Horng Sheu, and Robert Tarjan. Dynamic construction of the lovasz local lemma. Manuscript, April 2026., 2026.
[23] Bernhard Haeupler and Anton Paramonov. Maintaining random assignments under adversarial dynamics. arXiv preprint arXiv:2604.05606, 2026. doi:10.48550/arXiv.2604.05606.
[24] Monika Henzinger and Pan Peng. Constant-time dynamic $(\Delta+1)$ -coloring. ACM Trans. Algorithms, 18(2):16:1–16:21, 2022. doi:10.1145/3501403.
[25] Mohammad Shoaib Jamall. A coloring algorithm for triangle-free graphs. arXiv preprint, 2011. arXiv:1101.5721.
[26] Kumar Joag-Dev and Frank Proschan. Negative association of random variables with applications. The Annals of Statistics, pages 286–295, 1983.
[27] Anders Johansson. Asymptotic choice number for triangle free graphs. Technical report, Technical report 91-5, DIMACS, 1996.
[28] Jeong Han Kim. On brooks’ theorem for sparse graphs. Combinatorics, Probability and Computing, 4(2):97–132, 1995. doi:10.1017/S0963548300001528.
[29] Michael Molloy. The list chromatic number of graphs with small clique number, 2018. arXiv:1701.09133.
[30] Michael Molloy and Bruce Reed. Graph colouring and the probabilistic method, volume 23. Springer Science & Business Media, 2002.
[31] Michael Molloy and Bruce Reed. Colouring graphs when the number of colours is almost the maximum degree. Journal of Combinatorial Theory, Series B, 109:134–195, 2014. doi:10.1016/J.JCTB.2014.06.004.
[32] Robin A. Moser. A constructive proof of the lovász local lemma. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 343–350. ACM, 2009. doi:10.1145/1536414.1536462.
[33] Robin A. Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. J. ACM, 57(2):11:1–11:15, 2010. doi:10.1145/1667053.1667060.
[34] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the chernoff–hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. doi:10.1137/S0097539793250767.
[35] Seth Pettie and Hsin-Hao Su. Fast distributed coloring algorithms for triangle-free graphs. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, volume 7966 of Lecture Notes in Computer Science, pages 681–693. Springer, 2013. doi:10.1007/978-3-642-39212-2_59.
[36] Bruce Reed. $\omega$ , $\Delta$ , and $\chi$ . Journal of Graph Theory, 27(4):177–212, 1998. doi:10.1002/(SICI)1097-0118(199804)27:4\%3C177::AID-JGT1\%3E3.0.CO;2-K.
[37] Bruce Reed. The list colouring constants. Journal of Graph Theory, 31(2):149–153, 1999. doi:10.1002/(SICI)1097-0118(199906)31:2\%3C149::AID-JGT8\%3E3.0.CO;2-\%23.
[38] Bruce Reed. A strengthening of brooks’ theorem. Journal of Combinatorial Theory, Series B, 76(2):136–149, 1999. doi:10.1006/JCTB.1998.1891.
[39] Bruce Reed and Benny Sudakov. Asymptotically the list colouring constants are 1. Journal of Combinatorial Theory, Series B, 86(1):27–37, 2002. doi:10.1006/JCTB.2002.2110.
[40] Terence Tao. Moser’s entropy compression argument. https://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression-argument/, 2009. Blog post on What’s New, August 5.
[41] Vadim G Vizing. Some unsolved problems in graph theory. Russian Mathematical Surveys, 23(6):125, 1968.

[bib.bib1] [1] Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. Beyond the lovász local lemma: Point to set correlations and their algorithmic applications. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 725–744. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00049.

[bib.bib2] [2] Noga Alon and Sepehr Assadi. Palette sparsification beyond ( $\Delta$ +1) vertex coloring. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, Virtual Conference, August 17-19, 2020, volume 176 of LIPIcs, pages 6:1–6:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.6.

[bib.bib3] [3] Noga Alon, Michael Krivelevich, and Benny Sudakov. Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Series B, 77(1):73–82, 1999. doi:10.1006/JCTB.1999.1910.

[bib.bib4] [4] Nikhil Bansal, Anupam Gupta, and Guru Guruganesh. On the lovász theta function for independent sets in sparse graphs. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 193–200. ACM, 2015. doi:10.1145/2746539.2746607.

[bib.bib5] [5] Soheil Behnezhad, Rajmohan Rajaraman, and Omer Wasim. Fully dynamic $(\Delta+1)$ -coloring against adaptive adversaries. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4983–5026. SIAM, 2025. doi:10.1137/1.9781611978322.169.

[bib.bib6] [6] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1671–1684. ACM, 2022. doi:10.1145/3519935.3520064.

[bib.bib7] [7] Anton Bernshteyn. The johansson-molloy theorem for dp-coloring. Random Structures & Algorithms, 54(4):653–664, 2019. doi:10.1002/RSA.20811.

[bib.bib8] [8] Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Deterministic dynamic maximal matching in sublinear update time. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 132–143. ACM, 2025. doi:10.1145/3717823.3718153.

[bib.bib9] [9] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022, LIPIcs, pages 20:1–20:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.20.

[bib.bib10] [10] Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1–20. SIAM, 2018. doi:10.1137/1.9781611975031.1.

[bib.bib11] [11] Sayan Bhattacharya, Martín Costa, Nadav Panski, and Shay Solomon. Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 3393–3440. SIAM, 2024. doi:10.1137/1.9781611977912.122.

[bib.bib12] [12] Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, and Shay Solomon. Fully dynamic $(\Delta+1)$ -coloring in $O(1)$ update time. ACM Trans. Algorithms, 18(2):10:1–10:25, 2022. doi:10.1145/3494539.

[bib.bib13] [13] Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022, LIPIcs, pages 17:1–17:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.17.

[bib.bib14] [14] Marthe Bonamy, Tom Kelly, Peter Nelson, and Luke Postle. Bounding $\chi$ by a fraction of $\Delta$ for graphs without large cliques. Journal of Combinatorial Theory, Series B, 157:263–282, 2022. doi:10.1016/J.JCTB.2022.06.002.

[bib.bib15] [15] Rowland Leonard Brooks. On colouring the nodes of a network. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 37(2), pages 194–197. Cambridge University Press, 1941.

[bib.bib16] [16] Aleksander B. G. Christiansen and Eva Rotenberg. Fully-dynamic $\alpha+2$ arboricity decompositions and implicit colouring. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4-8, 2022, volume 229 of LIPIcs, pages 42:1–42:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.42.

[bib.bib17] [17] Aleksander B. G. Christiansen, Eva Rotenberg, and Juliette Vlieghe. Sparsity-parameterised dynamic edge colouring. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024, Helsinki, Finland, June 12-14, 2024, volume 294 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SWAT.2024.20.

[bib.bib18] [18] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1201–1214. ACM, 2023. doi:10.1145/3564246.3585111.

[bib.bib19] [19] Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1937–1945. SIAM, 2019. doi:10.1137/1.9781611975482.117.

[bib.bib20] [20] Maxime Flin and Magnús M. Halldórsson. Faster dynamic $(\Delta+1)$ -coloring against adaptive adversaries. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, volume 334 of LIPIcs, pages 79:1–79:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.79.

[bib.bib21] [21] David A. Grable and Alessandro Panconesi. Fast distributed algorithms for {Brooks-Vizing} colourings. In Howard J. Karloff, editor, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA, pages 473–480. ACM/SIAM, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314829.

[bib.bib22] [22] Bernhard Haeupler, Slobodan Mitrovic, Srikkanth Ramachandran, Wen-Horng Sheu, and Robert Tarjan. Dynamic construction of the lovasz local lemma. Manuscript, April 2026., 2026.

[bib.bib23] [23] Bernhard Haeupler and Anton Paramonov. Maintaining random assignments under adversarial dynamics. arXiv preprint arXiv:2604.05606, 2026. doi:10.48550/arXiv.2604.05606.

[bib.bib24] [24] Monika Henzinger and Pan Peng. Constant-time dynamic $(\Delta+1)$ -coloring. ACM Trans. Algorithms, 18(2):16:1–16:21, 2022. doi:10.1145/3501403.

[bib.bib25] [25] Mohammad Shoaib Jamall. A coloring algorithm for triangle-free graphs. arXiv preprint, 2011. arXiv:1101.5721.

[bib.bib26] [26] Kumar Joag-Dev and Frank Proschan. Negative association of random variables with applications. The Annals of Statistics, pages 286–295, 1983.

[bib.bib27] [27] Anders Johansson. Asymptotic choice number for triangle free graphs. Technical report, Technical report 91-5, DIMACS, 1996.

[bib.bib28] [28] Jeong Han Kim. On brooks’ theorem for sparse graphs. Combinatorics, Probability and Computing, 4(2):97–132, 1995. doi:10.1017/S0963548300001528.

[bib.bib29] [29] Michael Molloy. The list chromatic number of graphs with small clique number, 2018. arXiv:1701.09133.

[bib.bib30] [30] Michael Molloy and Bruce Reed. Graph colouring and the probabilistic method, volume 23. Springer Science & Business Media, 2002.

[bib.bib31] [31] Michael Molloy and Bruce Reed. Colouring graphs when the number of colours is almost the maximum degree. Journal of Combinatorial Theory, Series B, 109:134–195, 2014. doi:10.1016/J.JCTB.2014.06.004.

[bib.bib32] [32] Robin A. Moser. A constructive proof of the lovász local lemma. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 343–350. ACM, 2009. doi:10.1145/1536414.1536462.

[bib.bib33] [33] Robin A. Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. J. ACM, 57(2):11:1–11:15, 2010. doi:10.1145/1667053.1667060.

[bib.bib34] [34] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the chernoff–hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. doi:10.1137/S0097539793250767.

[bib.bib35] [35] Seth Pettie and Hsin-Hao Su. Fast distributed coloring algorithms for triangle-free graphs. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, volume 7966 of Lecture Notes in Computer Science, pages 681–693. Springer, 2013. doi:10.1007/978-3-642-39212-2_59.

[bib.bib36] [36] Bruce Reed. $\omega$ , $\Delta$ , and $\chi$ . Journal of Graph Theory, 27(4):177–212, 1998. doi:10.1002/(SICI)1097-0118(199804)27:4\%3C177::AID-JGT1\%3E3.0.CO;2-K.

[bib.bib37] [37] Bruce Reed. The list colouring constants. Journal of Graph Theory, 31(2):149–153, 1999. doi:10.1002/(SICI)1097-0118(199906)31:2\%3C149::AID-JGT8\%3E3.0.CO;2-\%23.

[bib.bib38] [38] Bruce Reed. A strengthening of brooks’ theorem. Journal of Combinatorial Theory, Series B, 76(2):136–149, 1999. doi:10.1006/JCTB.1998.1891.

[bib.bib39] [39] Bruce Reed and Benny Sudakov. Asymptotically the list colouring constants are 1. Journal of Combinatorial Theory, Series B, 86(1):27–37, 2002. doi:10.1006/JCTB.2002.2110.

[bib.bib40] [40] Terence Tao. Moser’s entropy compression argument. https://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression-argument/, 2009. Blog post on What’s New, August 5.

[bib.bib41] [41] Vadim G Vizing. Some unsolved problems in graph theory. Russian Mathematical Surveys, 23(6):125, 1968.

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contributions

Result 1.

Result 2.

Our techniques

Perspective: dynamic entropy compression

Independent and concurrent works

2 Preliminaries

Notation.

Dynamic graphs.

Balls into bins

Proposition 1 (​​[34, 29]).

Proof sketch.

Concentration Inequality

Proposition 2 (Chernoff-Hoeffding bound; cf. [30]).

Entropy compression

Lemma 3.

Proof.

3 An 𝑶⁢(𝚫𝟐⁢𝐥𝐨𝐠⁡𝒏) Update Time Algorithm

Theorem 4 (Formalizing Result 2).

3.1 Setup

Lemma 5.

3.2 The PartialColor Algorithm

Observation 6.

Proof.

Lemma 7.

Proof.

Part 1.

Part 2.

The compression scheme

Observation 8.

Proof.

Lemma 9.

Proof.

Improved bounds for oblivious adversaries

Proof of Lemma 5.

3.3 Concluding the Proof of Theorem 4

Proof of Theorem 4.

4 A 𝚫𝒐⁢(𝟏)⁢𝐥𝐨𝐠⁡𝒏 Update Time Algorithm

Theorem 10 (Formalizing Result 1).

Lemma 11.

Invariant 11.

Lemma 12.

Proof.

Lemma 13.

Proof.

Lemma 14.

Proof.

References

Proposition 1 ([34, 29]).

3 An $O(\Delta^{2}\log{n})$ Update Time Algorithm

4 A $\Delta^{o(1)}\log{n}$ Update Time Algorithm