Abstract

The dichromatic number of a digraph is the minimum number of colors needed to partition its vertex set into acyclic subdigraphs. A biclique is a set of vertices inducing all possible pairs of opposite arcs. For a digraph \(D\), define \(\tilde{\Delta}(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}\).

We prove that, for every fixed integer \(b\in\mathbb{N}\), every digraph \(D\) with \(\tilde{\Delta}(D) = \Delta\) being sufficiently large with respect to \(b\) either contains a biclique whose size exceeds \(\Delta-2b\) or has dichromatic number at most \(\Delta-b\).

This extends a classical result of Reed to the directed setting and supports a conjecture of the present authors. Furthermore, the theorem is tight, as for all integers \(b\) and \(\Delta\geqslant 3b\) there exists a digraph \(D\) with \(\tilde{\Delta}(D)= \Delta\), dichromatic number \(\Delta-b+1\), and whose largest biclique has size \(\Delta-2b+1\).

1 Introduction↩︎

It is well-known that the chromatic number \(\chi(G)\) of a graph \(G\) is bounded above by \(\Delta(G)+1\), where \(\Delta(G)\) denotes the maximum degree of \(G\). This bound is achieved by complete graphs, which motivates the study of the relationships between \(\chi(G)\), \(\Delta(G)\), and the clique number \(\omega(G)\) of a graph \(G\). As a first step in this direction, Brooks [1] obtained a seminal result stating that every graph \(G\) satisfies \[\chi(G) \leqslant\max \{\Delta(G), \omega(G)\},\] unless \(\Delta(G)=2\) and \(G\) contains an odd cycle. Pushing this direction further, in 1977 Borodin and Kostochka [2] posed a celebrated conjecture stating that \[\chi(G) \leqslant\max \{\Delta(G)-1, \omega(G)\}\] holds for every graph \(G\) with \(\Delta(G)\geqslant 9\). Even though the conjecture is still open in general, Reed [3] proved that it holds for graphs \(G\) with \(\Delta(G)\geqslant 10^{10}\). Moreover, in 1998 Reed [4] conjectured that these inequalities are just the tip of the iceberg, and posed the following famous conjecture.

Conjecture 1 ([4]). Every graph \(G\) satisfies \(\chi(G) \leqslant\lceil \frac{1}{2}(\Delta(G)+1 + \omega(G))\rceil\).

As supporting evidence for the conjecture, in the same paper Reed proved that, for every graph \(G\), \(\chi(G) \leqslant\tfrac{1}{2}\big(\Delta(G) + 1 + \omega(G)\big)\) holds whenever \(\Delta(G)\) is sufficiently large and \(\omega(G)\) is sufficiently close to \(\Delta(G)\); formally when \(\Delta(G) \geqslant\Delta_0\) and \(\omega(G) \geqslant(1-\varepsilon)\Delta(G)\) for some absolute constants \(\Delta_0\in \mathbb{N}\) and \(\varepsilon\in (0,1)\). This has the following two main consequences.

Corollary 1 ([4]). There exists \(\varepsilon>0\) such that every graph \(G\) satisfies \[\chi(G) \leqslant\lceil (1-\varepsilon)(\Delta(G)+1) + \varepsilon\omega(G)\rceil.\]

Corollary 2 ([4]). For every \(b\in \mathbb{Z}\), there exists \(\Delta_b\in \mathbb{N}\) such that every graph \(G\) with \(\Delta(G) \geqslant\Delta_b\) and \(\omega(G) \leqslant\Delta(G)-2b\) satisfies \(\chi(G) \leqslant\Delta(G)-b\).

Observe that Conjecture 1 is precisely the statement of Corollary 1 for \(\varepsilon= 1/2\). This gave rise to a line of research aimed at determining the largest value of \(\varepsilon>0\) for which Corollary 1 holds. The current best result is due to Hurley, Joannis de Verclos, and Kang [5], who proved that it holds for \(\varepsilon= 0.119\) for graphs with sufficiently large maximum degree. This improves on earlier results obtained by Bonamy, Perrett, and Postle [6] and by Delcourt and Postle [7].

Let us briefly discuss the sharpness of Corollary 2 and its connection to Conjecture 1. First, observe that the threshold \(\Delta_b\) in Corollary 2 must depend on \(b\). Indeed, for every integer \(b\in \mathbb{N}\), there exists a graph \(G\) with \(\Delta(G) = 6b+2\), \(\omega(G) = 4b+2\), and \(\chi(G) = 5b+3\). One example is the graph obtained from a \(5\)-cycle by blowing up each vertex into a clique of size \(2b+1\). In particular, such a graph does not satisfy the conclusion of Corollary 2, showing that \(\Delta_b\) must be at least \(6b+3\).

However, the dependence of \(\Delta_b\) on \(b\) might not be necessary under the stronger hypothesis \(\omega(G) \leqslant\Delta -2b-1\). Indeed, Conjecture 1 is easily seen to be equivalent to the following.

Conjecture 2. For every \(b\in \mathbb{Z}\) and every graph \(G\), if \(\omega(G) \leqslant\Delta-2b-1\) then \(\chi(G) \leqslant\Delta-b\).

Under the assumption that \(\Delta_b\) is arbitrarily large compared to \(b\), the condition \(\omega(G) \leqslant\Delta-2b\) of Corollary 2 might not be optimal, as it is known to be tight only up to an \(o(b)\) term (see the proof of [4]).

The goal of this paper is to extend Corollary 2 to the directed setting, building on earlier work extending the aforementioned results. To this end, let us define three digraph parameters that respectively extend \(\chi\), \(\Delta\), and \(\omega\) to the directed setting. Here, an extension of a graph parameter is understood in the following sense: if \(D\) is a symmetric digraph (that is, \(uv\) is an arc of \(D\) if and only if \(vu\) is), the value of the digraph parameter on \(D\) coincides with the value of the corresponding graph parameter on the underlying graph of \(D\). This is indeed the case for \(\vec{\chi}\), \(\tilde{\Delta}\), and \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}\) defined as follows.

Let \(D\) be a digraph. We let \(\tilde{\Delta}(D)\) denote the maximum geometric mean of the in- and out-degrees of the vertices of \(D\), that is \(\tilde{\Delta}(D) = \max \{ \sqrt{d^-(v)\cdot d^+(v)} : v \in V(D) \}\). A biclique of \(D\) is a set of vertices inducing a complete digraph, which is a digraph containing all possible arcs. The biclique number \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D)\) of \(D\) is the size of the largest biclique of \(D\). The dichromatic number of \(D\), denoted by \(\vec{\chi}(D)\), is the smallest \(k\in \mathbb{N}\) for which \(D\) admits a partition \(V_1,\dots,V_k\) of its vertex-set such that \(D[V_i]\) is acyclic for every \(i\in [k]\).

Similar to the undirected case, relationships linking \(\vec{\chi}\), \(\tilde{\Delta}\), and \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}\) have recently gained interest. This started with a generalization of Brooks’ theorem obtained first by Jacob and Meyniel [8] and rediscovered independently by Mohar [9], which implies that every digraph \(D\) satisfies \[\vec{\chi}(D) \leqslant\max \{ \lceil\tilde{\Delta}(D)\rceil, \overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D)\},\] unless \(\tilde{\Delta}(D) = 1\) and \(D\) contains a directed cycle, or \(\tilde{\Delta}(D) = 2\) and \(D\) contains a symmetric odd cycle (see also [10] for alternative proofs and [11]–[14] for more general results).

Going one step further, Harutyunyan, Kawarabayashi, Picasarri-Arrieta, and Puig i Surroca [15] recently obtained that every digraph \(D\) with \(\tilde{\Delta}(D)\) being sufficiently large satisfies \[\vec{\chi}(D) \leqslant\max \{ \lceil\tilde{\Delta}(D)\rceil-1, \overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D)\},\] unless \(D\) is a very specific obstruction. This generalizes the aforementioned result of Reed [3], which itself supports the conjecture of Borodin and Kostochka [2]. Moreover, Kawarabayashi and Picasarri-Arrieta [16] recently posed the following conjecture, which, if true, implies both Conjecture 1 and an independent conjecture posed by Harutyunyan and Mohar [17].

Conjecture 3 ([16]). Every digraph \(D\) satisfies \(\vec{\chi}(D) \leqslant\lceil \tfrac{1}{2}(\tilde{\Delta}(D) + 1 + \overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D))\rceil\).

Generalizing Corollary 1, in the same paper they obtained the following, whose proof is inspired by the recent short proof of Corollary 1 due to King and Reed [18].

Theorem 1 ([16]). There exists \(\varepsilon>0\) such that every digraph \(D\) satisfies \[\vec{\chi}(D) \leqslant\lceil (1-\varepsilon)(\tilde{\Delta}(D) + 1) + \varepsilon\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D)\rceil.\]

Building on a result of Picasarri-Arrieta [19], they also obtained that every oriented graph \(D\) (that is, a digraph with biclique number \(1\)) with underlying graph \(G\) satisfies \(\vec{\chi}(D) \leqslant\tfrac{1}{3}\Delta(G)+2\) and \(\vec{\chi}(D) \leqslant\tfrac{1}{\sqrt{2}} \tilde{\Delta}(D) +2\) (see [20]). This improves on earlier bounds obtained respectively by Harutyunyan and Mohar [17], Golowich [21], and Steiner [22].

It follows from Theorem 1 that every digraph \(D\) with \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D) \leqslant\tilde{\Delta}(D)-\frac{1}{\varepsilon}(b+2)\) satisfies \(\vec{\chi}(D) \leqslant\tilde{\Delta}(D) - b\). In view of Corollary 2 and Conjectures 2 and 3, this condition is certainly not optimal. In the present paper, we prove the following sufficient condition for a digraph \(D\) to be \((\tilde{\Delta}(D)-b)\)-colorable, which generalizes Corollary 2 to the directed setting and supports Conjecture 3.

theoremmainthm For every \(b\in \mathbb{Z}\), there exists \(\Delta_b\in \mathbb{N}\) such that every digraph \(D\) with \(\tilde{\Delta}(D) \geqslant\Delta_b\) and \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D) \leqslant\tilde{\Delta}(D)-2b\) satisfies \(\vec{\chi}(D) \leqslant\tilde{\Delta}(D)-b\).

Corollary 2 indeed corresponds to the restriction of Theorem [thm:main] to symmetric digraphs. However, we note that Corollary 2 is known to hold with \(\Delta_b\) being at most linear in \(b\), while our proof requires at least \(\Delta_b \geqslant 2^{\Omega(b^2)}\). We are aware that sharper arguments could likely reduce the required value of \(\Delta_b\) substantially. However, we chose to prioritize the simplicity of the proof, particularly since a linear bound seems out of reach with our approach. In particular, our argument is somewhat shorter than Reed’s original one.

We further note that, in the statement of Theorem [thm:main], in contrast to the undirected case, the condition \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D) \leqslant\tilde{\Delta}(D)-2b\) is best possible. Indeed, for all pairs of integers \(b,\Delta\in \mathbb{N}\), there exists a digraph \(D\) such that \(\tilde{\Delta}(D) \geqslant\Delta\), which satisfies \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D) = \tilde{\Delta}(D) -2b+1\) and \(\vec{\chi}(D) = \tilde{\Delta}(D) -b+1\). Such a digraph can be obtained from a biclique on \(\Delta+1\) vertices by blowing up \(b\) vertices into directed triangles.

Finally, let us mention that we decided to state Theorem [thm:main] in terms of the parameter \(\tilde{\Delta}\) because it is in line with numerous papers [15]–[17], [21], but that the same statement holds for many other degree parameters. To see this, for any function \(f\colon \mathbb{N}^2 \to \mathbb{R}\), let \(\Delta_f\) be the maximum degree parameter corresponding to \(f\), that is, for every digraph \(D\), let \[\Delta_f(D) = \max_{v\in V(D)} f(d^-(v),d^+(v)),\] Our proof can easily be adapted to show that Theorem [thm:main] holds with \(\Delta_f\) instead of \(\tilde{\Delta}\) whenever \(f\) is such that:

for every \(x,y\in \mathbb{N}\), \(f(x,y) \geqslant\min(x,y)\), and

for every \(a\in \mathbb{N}\), there exist \(b,\Delta_0\in \mathbb{N}\) such that, for every integer \(\Delta\geqslant\Delta_0\), we have \(f(\Delta-a, \Delta+b) \geqslant\Delta\) and \(f(\Delta+b, \Delta-a) \geqslant\Delta\). For instance, Theorem [thm:main] holds when \(\tilde{\Delta}\) is replaced by \(\Delta_{\max}\) or by the maximum arithmetic mean of the in- and out-degrees.

One of the most natural degree parameters for which our result remains open is the maximum out-degree \(\Delta^{\!+}\). Indeed, we do not even know whether it holds when restricted to oriented graphs. In this context, Kawarabayashi and Picasarri-Arrieta [16] proposed the following open problem.

Problem 4 ([16]). Show the existence of \(\varepsilon>0\) and \(\Delta_0\in \mathbb{N}\) such that every oriented graph \(D\) with \(\Delta^{\!+}(D)\geqslant\Delta_0\) satisfies \(\vec{\chi}(D) \leqslant(1-\varepsilon)\Delta^{\!+}(D)\).

It is a consequence of the Directed Brooks Theorem [8] that every oriented graph \(D\) with \(\Delta^{\!+}(D)\geqslant 2\) satisfies \(\vec{\chi}(D)\leqslant\Delta^{\!+}(D)\). It is also a consequence of a stronger result due to Harutyunyan, Kawarabayashi, Picasarri-Arrieta, and Puig i Surroca [15] (see [15]) that \(\vec{\chi}(D)\leqslant\Delta^{\!+}(D)-1\) holds when \(D\) is an oriented graph with \(\Delta^{\!+}(D)\) being sufficiently large. However, we note that already the following problem is open.

Problem 5. Show the existence of \(\Delta_0\in \mathbb{N}\) such that every oriented graph \(D\) with \(\Delta^{\!+}(D)\geqslant\Delta_0\) satisfies \(\vec{\chi}(D) \leqslant\Delta^{\!+}(D)-2\).

Bounding the dichromatic number of oriented graphs in terms of their maximum degree is at the heart of the following famous conjecture due to Erdős and Neumann-Lara (see [23]), which can be seen as a directed version of Johansson’s bound for triangle-free graphs [24].

Conjecture 6 ([23]). Every oriented graph \(D\) satisfies \(\vec{\chi}(D) = O(\Delta/ \log \Delta)\), where \(\Delta\) is the maximum degree of the underlying graph of \(D\).

The analogous conjecture in terms of \(\tilde{\Delta}\) has been posed by McDiarmid and Mohar, see [17].

2 Technical Overview↩︎

Our proof of Theorem [thm:main] combines structural and probabilistic arguments. We argue by contradiction and let \(D\) be a smallest counterexample. Our starting point is a partition of the vertex set of \(D\) into one sparse part (that is, a set of vertices whose out-neighborhood is sparse) and a collection of dense subdigraphs. This is done using a recent Dense Decomposition Lemma due to Harutyunyan, Kawarabayashi, Picasarri-Arrieta, and Puig i Surroca [15]. Previous work [15]–[17] already shows that the sparse vertices can be handled by a suitable random dicoloring argument. Consequently, the main difficulty lies in handling the dense sets. Harutyunyan, Kawarabayashi, Picasarri-Arrieta, and Puig i Surroca [15] developed the structural machinery based on the notion of saviors, which they use to prove the case \(b=2\) (and actually a stronger statement characterizing the exact obstructions to the (\(\tilde{\Delta}-1\))-dicolorability). Without any further ingredients, this machinery naturally yields only the weaker statement that all digraphs with biclique number \(\tilde{\Delta}- \Omega(b)\) have dichromatic number at most \(\tilde{\Delta}-b\). The main novelty of the present paper is the introduction of vertex identifications, which provides the additional flexibility needed to extend this approach and obtain the exact bound for every fixed \(b\).

We first show that every dense set contains a biclique on \((1-o(1))\tilde{\Delta}\) vertices, with at most \(O(b)\) exceptional vertices. The key notion in the structural part of the proof is that of a savior. Informally, a savior is a vertex inside the biclique that has sufficiently many neighbors outside it which are essentially “independent” of the biclique itself. Moreover, a savior needs to be in the common neighborhood of all exceptional vertices of the dense set. The fact that the exceptional set has size \(O(b)\) is crucial here. Since the Dense Decomposition Lemma is applied with a parameter \(\varepsilon_b\) chosen sufficiently small with respect to \(b\), the common neighborhood of all exceptional vertices inside the biclique remains large. This allows us to choose many saviors that are adjacent to all exceptional vertices.

In the random partial dicoloring constructed later, a savior is likely to see many colors appearing both inside and outside the biclique. Typically, a savior \(v\) with out-degree \(\tilde{\Delta}\) has at least \(b+1\) colors repeated in its out-neighborhood, making it easy to color. More precisely, no matter how we extend the coloring to the rest of its out-neighborhood, there will always be at least one color which remains free for \(v\). Using the minimality of our counterexample, we obtain that every dense set contains many saviors, roughly at least half of its vertices. This is large enough so that, with high probability, in the random partial dicoloring, many saviors will be rescuers, that is, saviors that are actually easy to color.

To get a bit more into details, we need to distinguish two kinds of dense sets, namely the loose and tight ones. A dense set is tight if its biclique is large, namely if it contains at least \(\tilde{\Delta}-3b+2\) vertices, while the biclique of a loose set can contain from \(\tilde{\Delta}- O_b(\log^3(\tilde{\Delta}))\) to \(\tilde{\Delta}-3b+1\) vertices. The distinction between loose and tight dense sets lies not in the existence of saviors, but in how much flexibility they provide.

Since a loose dense set contains relatively few vertices, each of its saviors has many neighbors outside the dense set, and this external flexibility alone is sufficient to complete the random dicoloring. The tight sets are considerably more delicate, and their structural analysis is the main technical contribution of the paper. Here, the large biclique has size \(\tilde{\Delta}-O(b)\), so although there are still many saviors, they may have only a few neighbors outside the dense set, which is no longer sufficient to complete the coloring directly. To recover the missing flexibility, we force carefully chosen pairs of exceptional vertices to receive the same color. Since every savior is adjacent to all exceptional vertices, identifying two exceptional vertices creates a repeated color in the neighborhood of every savior. These additional repeated colors compensate for the lack of neighbors outside the dense set.

The probabilistic part is thus carried out by coloring randomly the vertices of an auxiliary digraph \(D^\star\), obtained by identifying the aforementioned pairs of vertices inside the dense sets. Formally, we give a color to each vertex of \(D^\star\) uniformly at random, and then we uncolor all vertices of \(D^\star\) whose color appears in both their in- and out-neighborhoods. This yields a random partial dicoloring of \(D^\star\), and we interpret it as a random partial dicoloring of the original digraph, thereby introducing exactly the color equalities encoded by the identifications.

The crucial property is that tight dense sets admit enough additional structure compared to the loose sets, so that \(D^\star\) does not differ too much from \(D\). In particular, the required identifications increase the maximum degree by only \(O(b)\) and preserve the sparsity of the sparse vertices. The structural properties established in the previous sections guarantee that every bad event, which is of the form “the random partial dicoloring cannot be extended to the \(i\)th dense set” or “the random partial dicoloring cannot be extended to the \(i\)th sparse vertex” is sufficiently unlikely. Moreover, each bad event depends on only polynomially many other bad events, while its probability is super-polynomially small, which allows us to apply the Lovász Local Lemma. The polynomial bound on the dependencies of the bad events ultimately relies on the fact that the auxiliary digraph \(D^\star\) preserves distances up to a factor of three, which in turn follows from the refined structure of tight dense sets.

3 Preliminaries↩︎

3.1 Definitions and notation↩︎

For any positive integer \(k\), we denote by \([k]\) the set of integers \(\{1,\dots,k\}\). For any set \(X\), we denote by \(\binom{X}{2}\) the set of pairs of elements of \(X\).

Our notation on digraphs follows [25]. Let \(D\) be a digraph. The vertex-set of \(D\) is denoted by \(V(D)\) and its arc-set by \(A(D)\). A digon of \(D\) is a pair of arcs of \(D\) in opposite directions between the same vertices. A digraph is symmetric if each of its arcs belongs to a digon. The underlying graph of \(D\) is the undirected graph with vertex-set \(V(D)\) in which \(uv\) is an edge if and only if \(uv\) or \(vu\) is an arc of \(D\). The complement of \(D\), denoted by \(\overline{D}\), is the digraph with vertex set \(V(D)\) that contains all arcs except those of \(D\). A matching of \(D\) is a set of pairwise disjoint edges of the underlying graph \(G\) of \(D\). We denote by \(\nu(D)\) the maximum cardinality of a matching of \(D\).

Let \(v\) be a vertex of \(D\). The out-neighborhood of \(v\) in \(D\), denoted by \(N^+_D(v)\), is the set of vertices \(w\in V(D)\) such that \(vw\in A(D)\). Similarly, the in-neighborhood \(N^-_D(v)\) of \(v\) is the set of vertices \(u\) such that \(uv\in A(D)\). The out-degree \(d^+_D(v)\) and the in-degree \(d^-_D(v)\) of \(v\) are the number of out-neighbors and in-neighbors of \(v\), respectively. We denote by \(N_D(v)\) the neighborhood of \(v\) in \(D\), which is the union of its in- and out-neighborhoods. We finally denote by \(N_D^\pm(v)\) the set of vertices that are linked with \(v\) by a digon, that is, \(N_D^\pm(v) = N^+_D(v) \cap N^-_D(v)\). For each of the notations above, we omit the subscript when \(D\) is clear from the context. We use two notions of maximum degrees for \(D\), namely: \[\Delta_{\max}(D) = \max_{v\in V(D)} \max \{ d^+(v), d^-(v)\}\text{and}\tilde{\Delta}(D) = \max_{v\in V(D)} \sqrt{d^-(v)\cdot d^+(v)}.\]

Let \(X\subseteq V(D)\) be any subset of vertices of \(D\). The subdigraph of \(D\) induced by \(X\), denoted by \(D[X]\), is the digraph with vertex-set \(X\) containing all arcs of \(D\) with both extremities in \(X\). We denote by \(D/X\) the digraph obtained from \(D\) by identifying \(X\) into a single vertex \(s\). Formally, \(D/X\) has vertex-set \((V(D) \setminus X) \cup \{s\}\) and contains all arcs of \(D[V(D)\setminus X]\) as well as the arcs \[\{us : ux\in A(D) \text{ for some x\in X}\} \cup \{s u : xu\in A(D) \text{ for some x\in X}\}.\]

Let \(Y\subseteq V(D)\) be disjoint from \(X\). We say that \(X\) dominates \(Y\) and that \(Y\) is dominated by \(X\) if \(D\) contains all arcs of the form \(xy\) for \(x\in X\) and \(y\in Y\). We further say that a vertex \(x\) dominates \(Y\) if \(\{x\}\) dominates \(Y\), and similarly that a vertex \(y\) is dominated by \(X\) if \(\{y\}\) is dominated by \(X\).

A biclique of \(D\) is a set of vertices inducing a complete digraph, which is a digraph containing all possible arcs. The biclique number \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D)\) of \(D\) is the size of the largest biclique of \(D\). For any \(\ell\), let \(\mathscr{C}_\ell\) be the digraph with vertex-set \(\{u_0,u_1,\dots,u_{\ell-1}\}\) and arc-set \(\{u_iu_{i+1 \bmod \ell}: 0\leqslant i \leqslant\ell-1\}\). A directed cycle is a digraph isomorphic to \(\mathscr{C}_\ell\) for some \(\ell\geqslant 2\). A digraph is acyclic if it does not contain any directed cycle. Given an integer \(k\), a \(k\)-dicoloring of \(D\) is a coloring of its vertex-set \(\phi\colon V(D) \to [k]\) such that each color class \(\phi^{-1}(i)\) induces an acyclic subdigraph on \(D\). The dichromatic number of \(D\), denoted by \(\vec{\chi}(D)\), is the smallest \(k\in \mathbb{N}\) for which \(D\) admits a \(k\)-dicoloring.

3.2 Dicoloring tools↩︎

Along the proof, we often make use of the following easy and well-known observations.

Lemma 1. Let \(D\) be a digraph, \(S\subseteq V(D)\) be such that \(D[S]\) is acyclic, \(D/S\) be the digraph obtained by identifying \(S\) into a single vertex \(s\), and \(\phi^\star\) be a dicoloring of \(D/S\). Then \[\phi\colon v\mapsto \begin{cases} \phi^\star(v) & \text{if v\notin S}\\ \phi^\star(s) & \text{otherwise} \end{cases}\] is a dicoloring of \(D\).

Proof. Assume for a contradiction that \(D\), colored with \(\phi\), contains a monochromatic directed cycle \(\mathscr{C}\). Since \(S\) is acyclic, \(V(\mathscr{C}) \nsubseteq S\). Hence, either \(\mathscr{C}\) is disjoint from \(S\), or it contains a directed path that is internally disjoint from \(S\), with both extremities in \(S\). In both cases, \(D/S\) colored with \(\phi^\star\) contains a monochromatic directed cycle, a contradiction. ◻

Lemma 2. Let \(D\) be a digraph, \(S\subseteq V(D)\) be such that \(D[S]\) is acyclic, and \(\phi^\star\) be a dicoloring of \(D-S\). If \(\alpha\) is a color that is not used by \(\phi^\star\) in \(\bigcup_{s\in S}N^+(s)\) or in \(\bigcup_{s\in S}N^-(s)\), then \[\phi\colon v\mapsto \begin{cases} \phi^\star(v) & \text{if v\notin S}\\ \alpha & \text{otherwise} \end{cases}\] is a dicoloring of \(D\).

Proof. Assume for a contradiction that \(D\), colored with \(\phi\), contains a monochromatic directed cycle \(\mathscr{C}\). Then \(V(\mathscr{C}) \nsubseteq S\), as \(D[S]\) is acyclic. Furthermore, \(V(\mathscr{C}) \nsubseteq V(D)\setminus S\), for otherwise \(\mathscr{C}\) would be a monochromatic directed cycle of \(D-S\) colored with \(\phi^\star\). Therefore, \(\mathscr{C}\) contains an arc from \(S\) to \(V(D)\setminus S\) and an arc from \(V(D)\setminus S\) to \(S\). Since \(\mathscr{C}\) is monochromatic, this shows that \(\alpha\) appears in both \(\bigcup_{s\in S}N^+(s)\) and \(\bigcup_{s\in S}N^-(s)\), a contradiction. ◻

In particular, Lemma 2 implies that one can greedily color a digraph by repeatedly choosing an uncolored vertex \(v\), and assigning it a color that does not appear in \(N^-(v)\) or in \(N^+(v)\). This easy procedure shows that every digraph \(D\) satisfies \(\vec{\chi}(D) \leqslant\tilde{\Delta}(D)+1\).

Another useful application of Lemma 2 is the following. Suppose \(\{u,v\}\) is a pair of uncolored vertices with at most one arc between them. One may then assign both vertices the same color, provided that this color does not appear in \(N^+(u) \cup N^+(v)\) or in \(N^-(u) \cup N^-(v)\). This is useful when \(u\) and \(v\) have many common out-neighbors or in-neighbors, since in that case: (i) a common color is likely to exist, and (ii) every uncolored common out-neighbor acquires a repeated color in its in-neighborhood, making it easier to color afterwards using the greedy procedure above.

Throughout the proof, we use these two procedures repeatedly without explicitly referring to Lemma 2, for the sake of conciseness.

3.3 Dense decompositions↩︎

For the structural part of our proof, we use the following lemma due to Harutyunyan, Kawarabayashi, Picasarri-Arrieta, and Puig i Surroca [15], for which we first need a specific definition. Suppose that \(D\) is a digraph with \(\Delta_{\max}(D) = \Delta_{\rm m}\), and let \(d\) be any real number. We say that a vertex \(v\) is \(d\)-sparse (with respect to \(D\)) if the digraph induced by its out-neighborhood contains at most \(\Delta_{\rm m}(\Delta_{\rm m}-1) - d\Delta_{\rm m}\) arcs. The following lemma appears as a particular case of [15]. It can be seen as a general directed form of the so-called dense decompositions of graphs appearing in Molloy and Reed’s series of papers, see for instance [3], [4], [26]–[29]. Informally, it says that every digraph with sufficiently large maximum degree \(\Delta_{\rm m}\) can be decomposed into one set of sparse vertices and a collection of pairwise disjoint “dense sets” that behave like bicliques on roughly \(\Delta_{\rm m}\) vertices.

Lemma 3 (Dense Decomposition Lemma [15]). For every \(0 < \varepsilon< \frac{1}{2}\) there exists \(\Delta_{\rm DDL}(\varepsilon)\) such that the following holds. Let \(D\) be a digraph with \(\Delta_{\max}(D) = \Delta_{\rm m}\geqslant\Delta_{\rm DDL}(\varepsilon)\) and let \(d_{\rm m}= \log^3(\Delta_{\rm m})\). Then \(D\) admits a partition \((X_1, \ldots, X_t, S)\) of its vertex-set such that:

for every \(i\in [t]\), \(\Delta_{\rm m}- \frac{3}{\varepsilon} d_{\rm m}< |X_i| < \Delta_{\rm m}+1 + 4d_{\rm m}\);

for every \(i\in [t]\) and \(u\in V(D)\), \(u \in X_i\) if and only if \(|N^+(u) \cap X_i| \geqslant(1-\varepsilon) \Delta_{\rm m}\); and

vertices in \(S\) are \(d_{\rm m}\)-sparse.

From now on, for every \(\varepsilon\in (0,\tfrac{1}{2})\), we denote by \(\Delta_{\rm DDL}(\varepsilon)\) the smallest integer for which Lemma 3 holds. Intuitively speaking, the lemma above is useful when one wishes to extend some result known for sparse digraphs (that is, for digraphs in which all vertices are sparse) to a more general class of digraphs, as it provides structure on the vertices that are not sparse. This is typically our case with Theorem [thm:main]: if \(D\) is a \(d\)-sparse digraph (that is, all vertices in \(D\) are \(d\)-sparse) for some \(d>\log^3(\Delta)\), then it is known that \(D\) has dichromatic number at most \(\Delta-\Omega(d)\), see [16] (with \(\Delta\) being \(\Delta_{\max}(D)\) here).

3.4 Probabilistic tools↩︎

As mentioned above, our proof contains probabilistic arguments. The reader unfamiliar with the probabilistic method is referred to [30], [31]. We make use of the following three well-known results. We first need the symmetric version of the Lovász Local Lemma, due to Erdős and Lovász [32].

Lemma 4 (Lovász Local Lemma [32]). Let \(A_1,A_2,\dots,A_n\) be events in an arbitrary probability space. Suppose that each event \(A_i\) is mutually independent of a set of all the other events but at most \(d\), and that \(\mathbb{P}(A_i) \leqslant p\) for all \(1\leqslant i \leqslant n\). If \(4pd \leqslant 1\) then \(\mathbb{P}\left(\bigcap_{i=1}^n \overline{A_i}\right)>0\).

We further make use of the following consequence of the celebrated concentration inequality of Talagrand [33]. A proof of the following statement can be found in [15].

Lemma 5 (Talagrand [33]). Let \(X\) be a random variable valued in \(\mathbb{N}\), determined by \(n\) independent trials and satisfying the following for some integer \(r \geqslant 1\):

changing the outcome of any one trial can affect \(X\) by at most \(1\), and

for every \(k\in \mathbb{N}\), if \(X\geqslant k\) then there is a set of at most \(rk\) trials whose outcomes certify that \(X\geqslant k\). Then, for any real \(\lambda>126\sqrt{r\mathbb{E}(X)} + 344 r\), we have \(\mathbb{P}\left(|X- \mathbb{E}(X)| > \lambda \right) \leqslant 4\exp\left(\frac{-\lambda^2}{32 r(\mathbb{E}(X) + \lambda)} \right)\).

We finally make use of the celebrated concentration inequality of Azuma [34]. The following statement can be found in [31].

Lemma 6 (Azuma [34]). Let \(X\) be a random variable determined by \(n\) trials \(T_1,\ldots,T_n\), such that, for each \(1\leqslant i\leqslant n\), and any two possible sequences of outcomes \(t_1,\ldots,t_i\) and \(t_1,\ldots,t_{i-1},t'_i\), \[\Big|\,\mathbb{E}(X\,|\, T_1=t_1,\ldots,T_i=t_i)-\mathbb{E}(X\,|\, T_1=t_1,\ldots,T_{i-1}=t_{i-1},T_i=t'_i)\,\Big|\leqslant\delta_i.\] Then, for any real \(\lambda\geqslant 0\), we have \(\mathbb{P}(|X-\mathbb{E}(X)|>\lambda)\leqslant 2\exp\left(\frac{-\lambda^2}{2\sum_{i=1}^n \delta_i^2}\right)\).

4 Proof of Theorem [thm:main]↩︎

The remainder of the paper is devoted to the proof of Theorem [thm:main]. Roughly speaking, the proof proceeds in three steps, organized as follows. We first take a minimum counterexample \(D\), and exhibit a collection of structural properties on \(D\). These structural properties arise from the combination of the Dense Decomposition Lemma (applied to \(D\) with some \(\varepsilon\) small enough for a fixed \(b\)) and the minimality of \(D\). Once enough structure is obtained on \(D\), we manage to build an auxiliary graph \(D^\star\), whose structure is smoother than that of \(D\), with the guarantee that any dicoloring of \(D^\star\) with few colors yields a dicoloring of \(D\) with the same number of colors. We then use a pseudo-random coloring process to conclude on the colorability of \(D^\star\), and thus the one of \(D\), hence reaching a contradiction.

For convenience, let us first restate Theorem [thm:main] in the following equivalent form.

Theorem 2. For every \(b\in \mathbb{Z}\), there exists \(\Delta_b\in \mathbb{N}\) such that every digraph \(D\) with \(\tilde{\Delta}(D) \geqslant\Delta_b\) and \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D) \leqslant\tilde{\Delta}(D)-2b+2\) satisfies \(\vec{\chi}(D) \leqslant\tilde{\Delta}(D)-b+1\).

Proof. Let us fix \(b\in \mathbb{Z}\). As explained in Section 3.2, it is well-known that every digraph \(D\) satisfies \(\vec{\chi}(D)\leqslant\tilde{\Delta}(D)+1\). We henceforth assume that \(b\geqslant 1\). From now on, let \(\varepsilon_b= \frac{1}{24b}\). We let \(\Delta_b\) be the smallest integer so that, for every real number \(\Delta\geqslant\Delta_b\), each of the following inequalities holds: \[\renewcommand{\theequation}{\Delta\arabic{equation}} \begin{align} \Delta &\geqslant\Delta_{\rm DDL}(\varepsilon_b) + b-1,\tag{1}\\ 2\log^3(\Delta-b+1) &\geqslant\log^3(\Delta) \geqslant\tfrac{4}{5}\log^3(\Delta+b+1) +b+1,\tag{2}\\ \varepsilon_b^2\Delta &> \varepsilon_b\log^4(\Delta) > 16\log^3(\Delta) + 240b^2,\tag{3}\\ \log(\Delta) &\geqslant 2^8b,\tag{4}\\ \Delta\log^3(\Delta) &\geqslant 378b \Delta + 2^{35}\cdot 715^2 \Delta + 3b\log^3(\Delta) + 108b^2,\tag{5}\\ \left(1-\tfrac{6b}{\Delta}\right)^{\Delta/6b} &\geqslant 1/4, \tag{6}\\ \exp(-\log^2(\Delta))& \geqslant\max(8\exp(-2^{-50}\log^3(\Delta)),2\exp(-\Delta^{1/3}/144)),\tag{7}\\ \Delta^{1/3} & \geqslant b\cdot 2^{117b^2}\cdot \log^4(\Delta),\tag{8}\\ \exp(\log^2(\Delta)) &\geqslant 2^{19} \cdot (\Delta+b+1)^{13}\tag{9}. \end{align}\] Note that, for 6 , we use that \(\lim_{x\to +\infty} (1-\tfrac{1}{x})^x = 1/\mathop{\mathrm{e}}> 1/4\). We claim that the statement holds for this particular value of \(\Delta_b\). Assume that this is not the case, so there exists an integer \(\Delta \geqslant\Delta_b\) and a digraph \(H\) with:

\(\lfloor\tilde{\Delta}(H)\rfloor \leqslant\Delta\),

\(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(H) \leqslant\Delta-2b+2\), and

\(\vec{\chi}(H) \geqslant\Delta-b+2\). Among all such digraphs \(H\), we choose \(D=(V,A)\) of minimum order. In particular, it follows that every proper induced subdigraph of \(D\) has dichromatic number at most \(\Delta-b+1\). For the sake of conciseness, from now on, we let \(\Delta_{\rm m}\) denote \(\Delta_{\max}(D)\) and \(d= \log^3(\Delta)\).

4.1 Application of the Dense Decomposition Lemma↩︎

In this first part, we exhibit some structural properties of \(D\), arising from the combination of the dense decomposition lemma and the fact that \(D\) is a minimum counterexample to the desired statement. We first note that \(D\) being a minimum counterexample implies the following degree conditions.

Claim 7. Let \(v\) be an arbitrary vertex, then

\(\Delta-b+1 \leqslant\min \{d^+(v),d^-(v) \} \leqslant\Delta\), and

\(\max \{d^+(v), d^-(v)\} \leqslant\Delta+b+1\).

Proof of claim. Let \(v\) be an arbitrary vertex. Assume first that \(\min(d^-(v), d^+(v)) \leqslant\Delta - b\). By choice of \(D\), there exists a \((\Delta-b+1)\)-dicoloring \(\phi^\star\) of \(D-v\), which can be extended to \(D\) by choosing for \(v\) a color of \([\Delta-b+1]\) that is not appearing in its in- or out-neighborhood. This contradicts \(\vec{\chi}(D) > \Delta-b+1\), showing the first inequality.

Next, if \(\min \{d^+(v),d^-(v)\} \geqslant\Delta+1\) then \(\sqrt{d^+(v) \cdot d^-(v)} \geqslant\Delta+1\), which in particular implies that \(\lfloor\tilde{\Delta}(D)\rfloor \geqslant\Delta+1\), a contradiction. This shows [enum:degrees951].

For [enum:degrees952], assume for a contradiction that \(\max \{d^+(v),d^-(v)\} \geqslant\Delta+b+2\), then \[d^+(v)\cdot d^-(v) \geqslant(\Delta-b+1) \cdot (\Delta+b+2) = (\Delta+1)^2 +(\Delta +1)-b(b+1) \geqslant(\Delta+1)^2,\] and in particular \(\lfloor\tilde{\Delta}(D)\rfloor \geqslant\Delta+1\), a contradiction. The claim follows. ◻

In particular, Claim 7 shows that \(\Delta_{\rm m}\) is close to \(\Delta\), which allows us to apply the Dense Decomposition Lemma and derive the following.

Claim 8. There exists a partition \((X_1,\dots,X_t,S)\) of \(V\) such that:

for every \(i\in [t]\), \(\Delta - \frac{4}{\varepsilon_b}d < |X_i| < \Delta + 5d\);

for every \(i\in [t]\) and \(u\in X_i\), \(|N^+(u) \cap X_i| \geqslant(1-\varepsilon_b)\Delta -b\);

for every \(i\in [t]\) and \(u\in V \setminus X_i\), \(|N^+(u) \cap X_i| \leqslant(1-\varepsilon_b)\Delta +b+1\); and

vertices in \(S\) are \((d/2)\)-sparse.

Proof of claim. By Claim 7, we have that \(\Delta-b+1 \leqslant\Delta_{\rm m}\leqslant\Delta+b+1\). Therefore, Lemma 3 can be applied with \(\varepsilon= \varepsilon_b\), as \[\Delta_{\rm m}\geqslant\Delta-b+1 \geqslant\Delta_{\rm DDL}(\varepsilon_b)\] by 1 . Hence, by Lemma 3, there exists a partition \((X_1,\dots,X_t,S)\) of \(V\) such that:

for every \(i\in [t]\), \(\Delta_{\rm m}- \frac{3}{\varepsilon_b} \log^3(\Delta_{\rm m}) < |X_i| < \Delta_{\rm m}+ 1+ 4\log^3(\Delta_{\rm m})\);

for every \(i\in [t]\) and \(u\in V\), \(u\in X_i\) if and only if \(|N^+(u) \cap X_i| \geqslant(1-\varepsilon_b)\Delta_{\rm m}\);

vertices in \(S\) are \(\log^3(\Delta_{\rm m})\)-sparse.

We claim that the same partition satisfies the statement of the claim. Recall that \(\Delta-b+1 \leqslant\Delta_{\rm m}\leqslant\Delta+b+1\). Therefore, by [proofclaim:dense95decomposition:a], for every \(i\in [t]\), we have \[|X_i| > \Delta-b - \tfrac{3}{\varepsilon_b}\log^3(\Delta+b+1) \geqslant\Delta - \tfrac{4}{\varepsilon_b}\log^3(\Delta)\] by 2 . Similarly, for every \(i\in [t]\), we have \[|X_i| < \Delta + b +1 + 4\log^3(\Delta+b+1) \leqslant\Delta + 5\log^3(\Delta),\] which shows [claim:dense95decomposition:i]. Let \(i\in [t]\) be an arbitrary index and \(u\) be an arbitrary vertex in \(X_i\). Then by [proofclaim:dense95decomposition:b] we have \[|N^+(u) \cap X_i| \geqslant(1-\varepsilon_b)\Delta_{\rm m}\geqslant(1-\varepsilon_b)(\Delta-b+1)\geqslant(1-\varepsilon_b)\Delta-b,\] which shows [claim:dense95decomposition:ii]. Similarly, by [proofclaim:dense95decomposition:b], for any vertex \(u\in V\setminus X_i\) we have \[|N^+(u) \cap X_i| \leqslant(1-\varepsilon_b)\Delta_{\rm m}\leqslant(1-\varepsilon_b)(\Delta+b+1)\leqslant(1-\varepsilon_b)\Delta+b+1,\] which shows [claim:dense95decomposition:iii]. Finally, [claim:dense95decomposition:iv] follows from [proofclaim:dense95decomposition:c] and the fact that \[\log^3(\Delta_{\rm m}) \geqslant\log^3(\Delta-b+1) \geqslant\tfrac{1}{2}\log^3(\Delta)\] by 2 . The claim follows. ◻

From now on, let us fix a partition \((X_1,\dots,X_t,S)\) of \(V\) guaranteed by Claim 8. For every \(i\in [t]\), we let \(D_i = D[X_i]\) and \(\nu_i = \nu(\overline{D_i)}\). Furthermore, from now on, for every \(i\in [t]\), we fix a maximum matching \(M_i=(u_jv_j)_{j\in [\nu_i]}\) of \(\overline{D_i}\), and we let \(U_i\) be the set of vertices spanned by \(M_i\), that is \[U_i = \bigcup_{j\in [\nu_i]} \{u_j,v_j\}.\] We finally let \(K_i = X_i \setminus U_i\). Observe that, by maximality of \(M_i\), \(K_i\) is a biclique. Our first goal is to bound \(\nu_i\) for every \(i\in [t]\), hence showing that each \(D_i\) is almost a complete digraph. For this, we first need the following technical observation that we use several times later on.

Claim 9. Let \(i\in [t]\), \(M=(x_jy_j)_{j\in [\nu]}\) be a matching of \(\overline{D_i}\) of size \(\nu \leqslant 2b+1\), and \(U\) be the set of vertices spanned by \(M\). There exists a \((\Delta-b+1)\)-dicoloring \(\phi\) of \(D-(X_i\setminus U)\) such that, for every \(j\in [\nu]\), \(\phi(x_j) = \phi(y_j)\).

Proof of claim. By minimality of \(D\), there exists a \((\Delta-b+1)\)-dicoloring \(\phi\) of \(D-X_i\). By definition of a matching in \(\overline{D_i}\), for every \(j\), there is at most one arc between \(x_j\) and \(y_j\) in \(D\). We can thus extend \(\phi\) to \(U\) by assigning, for every \(j\in [\nu]\), a common color to \(\{x_j,y_j\}\) that is not already appearing in \(N^+(x_j) \cup N^+(y_j)\). Note that such a color is available because \(x_j\) and \(y_j\) have a large fraction of their out-neighbors in \(X_i\), which are still uncolored at that stage. Indeed, the number of already colored vertices in \(N^+(x_j) \cup N^+(y_j)\) is at most \[\begin{align} &|N^+(x_j)\setminus X_i| + |N^+(y_j) \setminus X_i| + |U|\\ &= d^+(x_j) + d^+(y_j) - |N^+(x_j)\cap X_i| - |N^+(y_j) \cap X_i| + |U|\\ &\leqslant 2(\Delta+b+1) -2((1-\varepsilon_b)\Delta - b) + (4b+2) &\text{by Claims~\ref{claim:degrees} and~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:ii},}\\ &= 2\varepsilon_b\Delta + 8b+4\\ &\leqslant\Delta-b &\text{by choice of \varepsilon_b and~\eqref{eq:largeDelta:3}.} \end{align}\] The claim follows. ◻

We are now ready to bound \(\nu_i\) for every \(i\in [t]\).

Claim 10. For every \(i\in [t]\), \(\nu_i \leqslant 2b\). In particular, \(|U_i| \leqslant 4b\).

Proof of claim. Assume for a contradiction that \(\overline{D_i}\) contains a matching of size \(\nu=2b+1\), and let \(M=(x_jy_j)_{j\in [\nu]}\) be such a matching. Note that we take \(M\) of size precisely \(2b+1\), even though there might exist larger matchings. Let \(U\) be the set of vertices spanned by \(M\).

By Claim 9, there exists a \((\Delta-b+1)\)-dicoloring \(\phi\) of \(D-(X_i\setminus U)\) such that \(\phi(x_j) = \phi(y_j)\) for every \(j\in [\nu]\). We show that \(\phi\) can be extended to \(D\), hence contradicting \(\vec{\chi}(D) > \Delta-b+1\). Let \(L\) be the set of vertices in \(X_i\) that are dominated by \(U\), that is \[L = X_i \cap \bigcap_{u\in U} N^+(u).\] In particular, note that \(L\) is disjoint from \(U\). Finally, let \(R\) be the remaining vertices of \(X_i\), so \(R=X_i \setminus (U\cup L)\). Observe that \((U,L,R)\) partitions \(X_i\). Let us first point out that \(L\) is significantly large, as \[\begin{align} |L| &\geqslant|X_i| - \sum_{u\in U}|X_i \setminus N^+(u)|\\&\geqslant|X_i| - |U| \cdot \big( |X_i| - ((1-\varepsilon_b)\Delta - b) \big) &\text{by Claim~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:ii},}\\ &\geqslant\Delta -\tfrac{4}{\varepsilon_b}d - (4b+2)\cdot (\varepsilon_b\Delta + 5d + b) &\text{by Claim~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:i},}\\ &\geqslant\tfrac{1}{2}\Delta - (8b+4)\varepsilon_b\Delta &\text{by~\eqref{eq:largeDelta:3},}\\ &\geqslant 2\varepsilon_b\Delta. &\text{by choice of \varepsilon_b.} \end{align}\] This allows us to extend \(\phi\) to \(R\), by choosing, for each vertex \(r\in R\), a color that is not already appearing in \(N^+(r)\). Note that this is possible, since the number of colored vertices in \(N^+(r)\) is at most \[\begin{align} |N^+(r) \setminus L| &= d^+(r) - |L \cap N^+(r)|\\ &\leqslant(\Delta +b+1) - |L| + |X_i \setminus N^+(r)| &\text{by Claim~\ref{claim:degrees},}\\ &\leqslant(\Delta +b+1) - 2\varepsilon_b\Delta + |X_i| - ((1-\varepsilon_b)\Delta-b) &\text{by Claim~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:ii},}\\ &\leqslant(\Delta +b+1) -2\varepsilon_b\Delta + \varepsilon_b\Delta + 5d+b&\text{by Claim~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:i},}\\ &= (1-\varepsilon_b)\Delta +5d+2b+1 \\ &\leqslant\Delta-b &\text{by~\eqref{eq:largeDelta:3}.} \end{align}\] We finally extend the partial dicoloring to \(L\), by choosing for every vertex \(x\in L\) a color that is not already appearing in \(N^-(x)\). Recall that, by Claim 7, \(d^-(x) \leqslant\Delta+b+1\). Moreover, by definition, \(U\) dominates \(x\), and by choice of \(\phi\) at most \(\frac{1}{2}|U|\) colors are used on \(U\). Therefore, the number of colors appearing in the in-neighborhood of \(x\) is at most \[d^-(x) - \frac{1}{2}|U| \leqslant\Delta +b+1 - |M| = \Delta -b.\] This shows that \(\phi\) can be extended to \(D\), a contradiction. Therefore, \(\nu_i = |M_i| \leqslant 2b\), and by definition we have \(|U_i| = 2|M_i| \leqslant 4b\), as desired. ◻

We conclude this first part with the following technical claim, which is a consequence of Claim 8 [claim:dense95decomposition:iii] that we use several times later on.

Claim 11. For every \(i\in [t]\), \(X\subseteq X_i\), and \(L \subseteq V(D) \setminus X_i\), if \(|X|\geqslant(1-\tfrac{1}{2}\varepsilon_b)\Delta\) and \(|L|\leqslant 2b^2+b\), then there exists a matching of size \(|L|\) between \(X\) and \(L\) in \(\overline{D}\).

Proof of claim. Let \(u_1,\dots,u_{\ell}\) be an arbitrary labeling of \(L\), where \(\ell=|L|\), and let us show that there exists, in \(\overline{D}\), a matching \(x_1u_1,\dots,x_\ell u_\ell\), where \(x_j \in X\) for every \(j\in [\ell]\).

We show that such a matching can be constructed greedily. To see this, assume for a contradiction that there exists such a matching \(x_1u_1,\dots,x_{j}u_{j}\) for some \(j< \ell\) which cannot be extended to span \(u_{j+1}\). Then, in particular \[X \subseteq N^+(u_{j+1}) \cup \{x_1,\dots,x_j\},\] which implies that \[|N^+(u_{j+1}) \cap X_i| \geqslant|X| - j\\ \geqslant(1-\tfrac{1}{2}\varepsilon_b)\Delta - 2b^2-b \\ > (1-\varepsilon_b)\Delta + b+1,\] where the last inequality holds by 3 . Since \(u_{j+1} \in L\) and, by assumption \(L\cap X_i = \varnothing\), this is a contradiction to Claim 8 [claim:dense95decomposition:iii]. ◻

In the two next subsections, we exhibit the exact structure we make use of in the probabilistic analysis. For every \(i\in [t]\), we let \(\mathscr{Z}_i\) denote the set of vertices in \(V(D) \setminus X_i\) with less than \(\log^4(\Delta)\) in- and out-neighbors in \(X_i\), that is \[\mathscr{Z}_i = \left\{ z \in V(D) \setminus X_i : \max\Big(|N^-(z) \cap X_i|, |N^+(z) \cap X_i|\Big) < \log^4(\Delta) \right\}.\] Intuitively, if some vertex \(x\in K_i\) has a neighbor \(z\in \mathscr{Z}_i\) then, in a random partial coloring (which is defined later on), it is likely that \(x\) has a neighbor in \(K_i\) that receives the same color as \(z\), which makes \(x\) “easier” to color. Hence, if \(x\) has sufficiently many such neighbors in \(\mathscr{Z}_i\), then \(x\) will likely be “easy” to color in a random coloring. In this case, we will call \(x\) a savior.

Our goal is thus to show that each \(X_i\) has many saviors, implying that, in a random partial coloring, many vertices in \(X_i\) are easy to color. We can then extend such a coloring to \(X_i\) by keeping those easy vertices for the end.

For technical reasons, the exact definition of a savior for \(X_i\) actually depends on the order of \(D_i\). In the remainder of the proof, we thus distinguish two cases for \(D_i\). We say that \(D_i\) is tight if \(|X_i| \geqslant\Delta-3b+2\), and that it is loose otherwise (that is, \(|X_i| \leqslant\Delta-3b+1\)).

4.2 Structure of the loose dense sets↩︎

We start with the case of loose \(D_i\)’s, which is a good warm-up before the more technical case of tight \(D_i\)’s. For every \(i\in [t]\), we say that a vertex \(x\) is a loose \(i\)-savior if \(x\in K_i\) and \[|N^+(x) \cap \mathscr{Z}_i| \geqslant d^+(x) - \Delta+b.\] The following shows the precise structure we need for loose \(D_i\)’s.

Claim 12. For every \(i\in [t]\), if \(D_i\) is loose then there exist at least \(\frac{1}{2}\Delta\) distinct loose \(i\)-saviors.

Proof of claim. Let \(i\in [t]\) be such that \(D_i\) is loose. We prove that all vertices in \(K_i\) are loose \(i\)-saviors except at most \(b-1\) of them, hence showing that the number of loose \(i\)-saviors is at least \[\begin{align} |K_i| - b + 1 &\geqslant|X_i|-5b+1 &\text{by Claim~\ref{claim:matching95Di},}\\ &\geqslant\Delta - \tfrac{4}{\varepsilon_b}d - 5b +1 &\text{by Claim~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:i},}\\ &\geqslant\tfrac{1}{2}\Delta &\text{by~\eqref{eq:largeDelta:3}.} \end{align}\] Assume for a contradiction that there exist \(b\) distinct vertices \(y_1,\dots,y_b\in K_i\), none of which is a loose \(i\)-savior. For \(j\in [b]\), let \(L_j\) denote the set of out-neighbors of \(y_j\) outside \(X_i \cup \mathscr{Z}_i\), that is \(L_j = N^+(y_j) \setminus (X_i \cup \mathscr{Z}_i)\). Recall that, by definition, since \(y_j\) is not a loose \(i\)-savior, we have \(|N^+(y_j) \cap \mathscr{Z}_i| \leqslant d^+(y_j) - \Delta+b-1\). Therefore, we have: \[\begin{align} |L_j| &= |N^+(y_j) \setminus (X_i \cup \mathscr{Z}_i)| & \\ &= d^+(y_j) - |N^+(y_j) \cap X_i| - |N^+(y_j)\cap \mathscr{Z}_i| & \\ &\geqslant d^+(y_j) - (|X_i|-1) -|N^+(y_j) \cap \mathscr{Z}_i| &\text{as y_j \in X_i \setminus N^+(y_j),} \\ &\geqslant\Delta-b+2 -|X_i| &\text{as y_j is not a loose i-savior,}\\ &\geqslant 2b+1 &\text{as D_i is loose.} \end{align}\] For every \(j\), let thus \(L'_j\) be an arbitrary subset of \(L_j\) of size precisely \(2b+1\), and let \(L= \bigcup_{j\in [b]}L_j'\). Let finally \(u_1,\dots,u_{\ell}\) be an arbitrary labeling of the vertices in \(L\), where \(\ell = |L|\), so \(\ell \leqslant 2b^2+b\).

By Claim 11, applied with \(X=K_i \setminus\{y_1,\dots,y_b\}\), there exists, in \(\overline{D}\), a matching \(x_1u_1,\dots,x_{\ell}u_{\ell}\) such that \(x_j \in K_i\setminus \{y_1,\dots,y_b\}\) for every \(j\in [\ell]\). Note that Claim 11 can be applied as \(|L| \leqslant 2b^2+b\) and \[\begin{align} |K_i \setminus\{y_1,\dots,y_b\}| &= |X_i| - |U_i| - b \\ &\geqslant\Delta-\tfrac{4}{\varepsilon_b}d -5b &\text{by Claims~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:i} and~\ref{claim:matching95Di},}\\ &\geqslant(1-\tfrac{1}{2}\varepsilon_b)\Delta &\text{by~\eqref{eq:largeDelta:3}}. \end{align}\]

Let \(\phi\) be a \((\Delta-b+1)\)-dicoloring of \(D-(K_i\cup L)\), which exists by minimality of \(D\). Then, for every \(j\in [\ell]\), we extend \(\phi\) to \(\{x_j,u_j\}\) by choosing for these two vertices a color that is not already appearing in \(N^+(x_j) \cup N^+(u_j)\) or in \(N^-(x_j) \cup N^-(u_j)\). To see that such a color is indeed available, recall that by construction \(u_j \notin \mathscr{Z}_i\), which means that \(u_j\) has at least \(\log^4(\Delta)\) in-neighbors or \(\log^4(\Delta)\) out-neighbors in \(X_i\). Assume that \(u_j\) has at least \(\log^4(\Delta)\) out-neighbors in \(X_i\), the other case being symmetric. Therefore, since the vertices in \(X_i\setminus (U_i \cup \{x_1,\dots,x_{j-1}\})\) are uncolored at that step, by Claim 10 we get that \(u_j\) has at least \[\log^4(\Delta) - |U_i| - (j-1) \geqslant\log^4(\Delta) -5b - 2b^2\] uncolored out-neighbors. Moreover, since \(x_j\in K_i\), \(x_j\) is linked with digons to all vertices in \(K_i\), and in particular \(x_j\) has at least \[|X_i| -|U_i| - (j-1) \geqslant|X_i|- 5b -2b^2\] uncolored out-neighbors. It follows that the number of colors appearing in \(N^+(x_j) \cup N^+(u_j)\) is at most \[\begin{align} &d^+(x_j) + d^+(u_j) - (\log^4(\Delta) -5b- 2b^2) - (|X_i|-5b-2b^2)&\\ &\leqslant 2\Delta- \log^4(\Delta)+ 4b^2 + 12b + 2 - |X_i| &\text{by Claim~\ref{claim:degrees},}\\ &\leqslant\Delta- \log^4(\Delta)+ \tfrac{4}{\varepsilon_b}d + 4b^2 + 12b + 2 &\text{by Claim~\ref{claim:dense95decomposition}\ref{claim:dense95decomposition:i},}\\ &\leqslant\Delta -b, &\text{by~\eqref{eq:largeDelta:3}.} \end{align}\] as desired. We then greedily extend the coloring to the vertices in \(K_i \setminus \{y_1,\dots,y_b\}\). Note that, by Claim 7, each of these vertices has in- or out-degree at most \(\Delta\), and has at least \(b\) in- and out-neighbors that are still uncolored (namely \(y_1,\dots,y_b\)). Therefore, the number of colors appearing in both the out- and in-neighborhood of every such vertex is at most \(\Delta-b\).

We finally extend the coloring to the remaining uncolored vertices, namely \(y_1,\dots,y_b\), by choosing for each of them a color that is not appearing in its out-neighborhood. Recall that \(y_j\) dominates \(L_j\) (and in particular, it dominates \(L_j'\)) and \(K_i \setminus y_j\). By construction, every color used on \(L_j'\) is also used on \(K_i\setminus y_j\). Therefore, since \(d^+(y_j) \leqslant\Delta+b+1\) by Claim 7, the number of colors appearing in the out-neighborhood of \(y_j\) is at most \[d^+(y_j) - |L_j'| \leqslant(\Delta+b+1) - (2b+1) = \Delta-b,\] as desired. This shows that \(\phi\) can be extended to \(D\), hence showing that \(\vec{\chi}(D) \leqslant\Delta-b+1\), a contradiction. ◻

4.3 Structure of the tight dense sets↩︎

We now move to the more technical case of tight \(D_i\)’s. The overall proof follows that for loose \(D_i\)’s, except that it requires a more careful analysis of the number of colors that can be “saved” on a savior.

The reader may note that the structural results of this section also hold for loose \(D_i\)’s. However, in order to make use of them in the next section, we need to identify certain vertices so as to ensure that they receive the same color via the random coloring process. Such identifications must be carried out carefully, as we need to ensure that the general structure of \(D\) is not affected too much. This is guaranteed when identifying two vertices within the same tight \(D_i\), but not within a loose \(D_i\).

Figure 1: An illustration of R_i, U_i^\star, K_i^\star, and Y_i. The matching M_i^\star is highlighted in orange. A solid digon between two sets illustrates the presence of all possible such digons. The dashed digon illustrates that vertices in U_i^\star are linked with digons to almost all vertices in K_i^\star. The dotted lines illustrate that |X_i\setminus N^\pm(r)|\geqslant13b for every r\in R_i. — Figure 1: An illustration of \(R_i\), \(U_i^\star\), \(K_i^\star\), and \(Y_i\). The matching \(M_i^\star\) is highlighted in orange. A solid digon between two sets illustrates the presence of all possible such digons. The dashed digon illustrates that vertices in \(U_i^\star\) are linked with digons to almost all vertices in \(K_i^\star\). The dotted lines illustrate that \(|X_i\setminus N^\pm(r)|\geqslant13b\) for every \(r\in R_i\).

We start with a few technical definitions, see Figure 1 for an illustration of these. For every \(i\in [t]\) we let \(R_i\) be the set of vertices in \(X_i\) that miss \(13b\) digons in \(X_i\), that is \[R_i = \{x\in X_i : |X_i\setminus N^\pm(x)| \geqslant13b\}.\] Note that \(R_i \subseteq U_i\): since \(K_i\) forms a biclique, every vertex \(x\in K_i\) satisfies \(|N^\pm(x)\setminus X_i| \leqslant|U_i|\) while \(|U_i| < 13b\) by Claim 10. In particular, since \(R_i \subseteq U_i\) then \(|R_i| \leqslant 4b\) by Claim 10.

Then, we let \(M_i^\star\) be maximum matching of \(\overline{D}[X_i \setminus R_i]\), we let \(\nu_i^\star = |M_i^\star|\), and we let \(U_i^\star\) be the set of vertices spanned by \(M_i^\star\). Observe that \(M_i^\star\) is also a matching of \(\overline{D_i}\), so by Claim 10, \[|U_i^\star| = 2\nu_i^\star \leqslant 2\nu_i \leqslant 4b.\] We further let \(K_i^\star = X_i \setminus (R_i \cup U_i^\star)\). Observe that, by definition of \(M_i^\star\), \(K_i^\star\) is a biclique. Finally, we let \[Y_i = K_i^\star \cap \bigcap_{u\in U_i^\star} N^\pm(u).\] By construction, we have the following three claims that will be useful in the probabilistic analysis later.

Claim 13. For every integer \(i\in [t]\), \(|K_i| \geqslant\Delta-\tfrac{4}{\varepsilon_b}d - 4b\) and \(|K_i^\star| \geqslant\Delta-\tfrac{4}{\varepsilon_b}d - 8b\).

Proof of claim. By definition, \(K_i = X_i \setminus U_i\), and \(K_i^\star = X_i \setminus (U_i^\star \cup R_i)\). Since \(R_i\subseteq U_i\), and both \(U_i\), \(U_i^\star\) have size at most \(4b\) by Claim 10, the result follows from Claim 8 [claim:dense95decomposition:i]. ◻

Claim 14. For every \(i\in [t]\) and every \(u\in U_i^\star\), we have \(|X_i\setminus N^\pm(u)| < 13b\) and \(Y_i \subseteq N^\pm(u)\). Moreover, for every \(i\in [t]\), \(|Y_i| \geqslant\frac{3}{4}\Delta\).

Proof of claim. We have that \(|N^\pm(u)\setminus X_i| < 13b\) as \(U_i^\star\) is chosen explicitly in \(X_i \setminus R_i\), and \(Y_i \subseteq N^\pm(u)\) by definition. For the last inequality, we have \[\begin{align} |Y_i| &\geqslant|K_i^\star| - 13b\cdot |U_i^\star|\\ &\geqslant\Delta -\tfrac{4}{\varepsilon_b}d- 8b - 52b^2 &\text{by Claims~\ref{claim:size95K} and~\ref{claim:matching95Di},}\\ &\geqslant\tfrac{3}{4}\Delta &\text{by~\eqref{eq:largeDelta:3}.} \end{align}\] The claim follows. ◻

Claim 15. For every \(i\in [t]\) and every \(uv\in M_i^\star\), if \(D_i\) is tight then \(|N^\pm(u)\cap N^\pm(v)| \geqslant\Delta-29b+2\).

Proof of claim. We have \[\begin{align} |N^\pm_D(u) \cap N^\pm_D(v)| &\geqslant|X_i| - |X_i \setminus N^\pm(u)|- |X_i \setminus N^\pm(v)|\\ &> |X_i| - 26b &\text{by Claim~\ref{claim:adjacency95Uis},}\\ &\geqslant\Delta -29b+2 &\text{as D_i is tight.} \end{align}\] The claim follows. ◻

We are finally ready to introduce the definition of saviors. We say that a vertex \(x\in X_i\) is a tight \(i^+\)-savior if each of the following holds:

\(x\in Y_i\),

\(d^+(x)\leqslant\Delta\), and

\(|N^+(x) \cap \mathscr{Z}_i| \geqslant d^+(x) - \Delta +b-\nu_i^\star\). Similarly, we say that \(x\in X_i\) is a tight \(i^-\)-savior if each of the following holds:

\(x\in Y_i\),

\(d^-(x)\leqslant\Delta\), and

\(|N^-(x) \cap \mathscr{Z}_i| \geqslant d^-(x) - \Delta +b-\nu_i^\star\). Finally, we say that \(x\in X_i\) is a tight \(i\)-savior if it is a tight \(i^+\)-savior or a tight \(i^-\)-savior. We conclude this part with the following key structural result.

Claim 16. For every \(i\in [t]\), there exist at least \(\frac{1}{2}\Delta\) distinct tight \(i\)-saviors.

Proof of claim. We prove that all vertices in \(Y_i\) are tight \(i\)-saviors except at most \(b-1\) of them, hence showing that the number of tight \(i\)-saviors is at least \[|Y_i| - b+1 \geqslant\tfrac{3}{4}\Delta - b+1 \geqslant\tfrac{1}{2}\Delta,\] where first inequality follows from Claim 14, and the second one from 3 . Assume for a contradiction that there exist \(b\) distinct vertices \(y_1,\dots,y_b\in Y_i\), none of which is a tight \(i\)-savior. For every \(j\in [b]\), let \[N_j = \begin{cases} N^+(y_j) & \text{if d^+(y_j) \leqslant\Delta}\\ N^-(y_j) & \text{otherwise.} \end{cases}\] Observe that \(|N_j| \leqslant\Delta\) by Claim 7. Further, for every \(j\in [b]\), let \[L_j = N_j \setminus (X_i \cup \mathscr{Z}_i).\] Note also that, by definition, since \(y_j\) is not a tight \(i\)-savior, we have \[|N_j \cap \mathscr{Z}_i| \leqslant|N_j| -\Delta + b-\nu^\star_i-1.\] Therefore, we can lower bound the size of \(L_j\) as follows: \[\begin{align} |L_j| &= |N_j \setminus (X_i \cup \mathscr{Z}_i)| & \\ &= |N_j| - |N_j \cap K_i^\star| - |N_j\cap U_i^\star| -|N_j\cap \mathscr{Z}_i|- |N_j\cap R_i| & \\ &= |N_j| - |K_i^\star| + 1 - 2\nu_i^\star - |N_j\cap \mathscr{Z}_i|- |N_j\cap R_i|&\text{as N_j \cap K_i^\star = K_i^\star \setminus \{y_j\},} \\ &\geqslant- |K_i^\star| +2+ \Delta-b - \nu_i^\star- |N_j\cap R_i| &\text{as y_j is not a tight i-savior,}\\ &\geqslant b-\nu_i^\star- |N_j\cap R_i| &\text{as K_i^\star is a biclique,} \end{align}\] where in the last inequality we further use the assumption that \(\overset{\text{\tiny\boldsymbol{\leftrightarrow}}}{\omega}(D) \leqslant\Delta-2b+2\). For every \(j\), let thus \(L_j'\) be an arbitrary subset of \(L_j\) of size precisely \(b-\nu_i^\star- |N_j\cap R_i|\), and let \(L= \bigcup_{j\in [b]}L_j'\). Let \(\ell = |L|\) and observe that \(\ell \leqslant b^2\). Let finally \(u_1,\dots,u_{\ell}\) be an arbitrary labeling of the vertices in \(L\).

Let \(M_R\) be a matching between \(R_i\) and \(K_i^\star \setminus \{y_1,\dots,y_b\}\) in \(\overline{D}\). Note that such a matching exists, as it can be constructed greedily. Indeed, for every \(r\in R_i\), we have \[\begin{align} |(K_i^\star \setminus \{y_1,\dots,y_b\}) \setminus N^\pm(r)| &\geqslant|X_i\setminus N^\pm(r)| - |U_i^\star| - |R_i| - b\\ &\geqslant13b- 4b - 4b- b &\text{by definition of R_i,}\\ &\geqslant 4b\\ &\geqslant|R_i|. \end{align}\] Let \(U_R\) be the set of vertices spanned by \(M_R\). By Claim 11 applied with \[X= K_i^\star \setminus (U_R \cup \{y_1,\dots,y_b\}),\] there exists, in \(\overline{D}\), a matching \(\{x_1u_1,\dots x_\ell u_\ell\}\), vertex-disjoint from \(M_R\), such that \(x_j \in K_i^\star \setminus \{y_1,\dots,y_b\}\) for every \(j\in [\ell]\). Note that it is possible to apply Claim 11 because \(|L|\leqslant b^2\) and \[\begin{align} |K_i^\star \setminus (U_R \cup \{y_1,\dots,y_b\})| &= |K_i^\star| - |R_i| - b \\ &\geqslant\Delta-\tfrac{4}{\varepsilon_b}d - 13b&\text{by Claim~\ref{claim:size95K},}\\ &\geqslant(1-\tfrac{1}{2}\varepsilon_b)\Delta &\text{by~\eqref{eq:largeDelta:3}}. \end{align}\]

Let \(\phi\) be a \((\Delta-b+1)\)-dicoloring of \(D-((X_i \cup L) \setminus (U_i^\star \cup U_R) )\), with the extra property that \(\phi(u) = \phi(v)\) for every \(uv \in M_i^\star \cup M_R\). Note that such a dicoloring exists by Claims 9 and 10 and the fact that \(M_i^\star \cup M_R\) is a matching of \(\overline{D_i}\) (up to uncoloring the vertices in \(L\)).

For every \(j\in [\ell]\), we extend \(\phi\) to \(\{x_j,u_j\}\) by choosing for these two vertices a color that is not already appearing in \(N^+(x_j) \cup N^+(u_j)\) or in \(N^-(x_j) \cup N^-(u_j)\). To see that such a color is available, recall that by construction \(u_j \notin \mathscr{Z}_i\), which means that \(u_j\) has at least \(\log^4(\Delta)\) in-neighbors or \(\log^4(\Delta)\) out-neighbors in \(X_i\). Assume that \(u_j\) has at least \(\log^4(\Delta)\) out-neighbors in \(X_i\), the other case being symmetric. Therefore, since the vertices in \(X_i\setminus (U_i^\star \cup U_R\cup \{x_1,\dots,x_{j-1}\})\) are uncolored at that step, we get that \(u_j\) has at least \[\log^4(\Delta) - |U_i^\star| - |U_R| - (j-1) \geqslant\log^4(\Delta) -4b - b^2\] uncolored out-neighbors, where in the inequality we use Claim 10 and the fact that \(M_i^\star \cup M_R\) is a matching of \(\overline{D_i}\). Moreover, since \(x_j\in K_i^\star\), \(x_j\) is linked with digons to all vertices in \(K_i^\star\), and in particular \(x_j\) has at least \[|K_i^\star| - |U_R\cap K_i^\star| - (j-1) \geqslant|K_i^\star|-2b - b^2\] uncolored out-neighbors. It follows that the number of colors appearing in \(N^+(x_j) \cup N^+(u_j)\) is at most \[\begin{align} &d^+(x_j) + d^+(u_j) - \log^4(\Delta)- |K_i^\star| + 6b +2b^2\\ &\leqslant\Delta- \log^4(\Delta) + \tfrac{4}{\varepsilon_b}d+ 2+16b + 2b^2 &\text{by Claims~\ref{claim:degrees} and~\ref{claim:size95K}}\\ &\leqslant\Delta -b, &\text{by~\eqref{eq:largeDelta:3}} \end{align}\] as desired. We then greedily extend the coloring to the uncolored vertices in \(K_i^\star \setminus \{y_1, \dots, y_b\}\). Note that, by Claim 7, each of these vertices has in- or out-degree at most \(\Delta\), and has at least \(b\) in- and out-neighbors that are still uncolored (namely \(y_1,\dots,y_b\)). Therefore, the number of colors appearing in both the out- and in-neighborhoods of every such vertex is at most \(\Delta-b\).

We finally extend the coloring to the remaining uncolored vertices, namely \(y_1,\dots,y_b\), by choosing for \(y_j\) a color that is not appearing in \(N_j\). Recall that, by construction, we have:

\(U_i^\star\subseteq N_j\),

\(L_j' \subseteq N_j\), and

\(U_R \cap X_i^\star \subseteq N_j\). Therefore, by construction of the current partial dicoloring, the number of colors appearing in \(N_j\) is at most \[|N_j| - \nu_i^\star - |L_j'| - |N_j \cap R_i| \leqslant|N_j| -b \leqslant\Delta-b\] by choice of \(L_j'\) and the fact that \(|N_j|\leqslant\Delta\). This shows that \(\phi\) can be extended to \(D\), hence showing that \(\vec{\chi}(D) \leqslant\Delta-b+1\), a contradiction. ◻

4.4 The random coloring process↩︎

The goal of this subsection is to define a specific random coloring process. In the next subsection, using probabilistic methods, we leverage on the structural properties obtained previously to show that, with positive probability, the partial dicoloring obtained by this process can be extended to \(D\), hence contradicting \(\vec{\chi}(D) > \Delta-b+1\).

Given a partial coloring \(\psi\) of a digraph \(H\), we denote by \(\mathop{\mathrm{Dom}}(\psi)\) its domain. For any subset of vertices \(X\subseteq V(H)\), we denote by \(\psi(X)\) the set of colors given by \(\psi\) on \(X\), that is \[\psi(X) = \{ \psi(x) : x\in X\cap \mathop{\mathrm{Dom}}(\psi)\}.\]

From now on, let \(\mathcal{I}\) be the set of indices \(i\in [t]\) such that \(D_i\) is tight. Let \(M^\star = \bigcup_{i\in \mathcal{I}}M_i^\star\). Let \(D^\star\) be the digraph obtained from \(D\) by identifying each \(\{u,v\}\in M^\star\) into a single vertex \(x_{u,v}\). Assign to each vertex \(v\in V(D^\star)\) a color from \([1,\lceil \Delta/2 \rceil]\) drawn independently and uniformly at random, and let \(\phi'\) be the obtained coloring. Note that \(\lceil\Delta/2\rceil < \Delta-b+1\) by 3 . Then, we simultaneously uncolor all the vertices \(v\in V(D^\star)\) whose color appear in both the in-neighborhood and the out-neighborhood of \(v\), that is,s such that \[\phi'(v) \in \phi'\Big(N^-_{D^\star}(v)\Big) \cap \phi'\Big(N^+_{D^\star}(v)\Big),\] and we let \(\phi^\star\) be the resulting partial coloring. Note that \(\phi^\star\) is a partial \((\Delta-b+1)\)-dicoloring of \(D^\star\), as any vertex is a sink or a source in its color class. Finally, let \(\phi\) be the partial coloring of \(D\) naturally derived from \(\phi^\star\), that is \[\begin{align} \mathop{\mathrm{Dom}}(\phi) = &~\Big\{v \in V(D) \cap V(D^\star) : v\in \mathop{\mathrm{Dom}}(\phi^\star)\Big\}\\ &\cup \Big\{u,v : \{u,v\}\in M^\star \text{~and~} x_{u,v} \in \mathop{\mathrm{Dom}}(\phi^\star)\Big\}, \end{align}\] and for every \(v\in \mathop{\mathrm{Dom}}(\phi)\), \[\phi(v) = \begin{cases} \phi^\star(v) & \text{if v\in V(D^\star)}\\ \phi^\star(x_{u,v}) & \text{otherwise, where u is such that \{u,v\} \in M^\star.} \end{cases}\] Note that \(\phi\) is a partial \((\Delta-b+1)\)-dicoloring of \(D\) by Lemma 1. For every vertex \(s\in S\), we say that \(\phi\) is \(s\)-extendable if at least one of the following holds:

\(\big|M^\star \cap \binom{N^+_D(s)}{2}\big| \geqslant 2b+1\), or

\(\big|\mathop{\mathrm{Dom}}(\phi) \cap N^+_D(s)\big| - \big|\phi\big(N^+_D(s)\big)\big| \geqslant 2b+1\). Note that the first property does not depend on \(\phi\).

For every \(i\in [t]\), we say that a vertex \(x\) is a loose \(i\)-rescuer (with respect to \(\phi\)) if \(x\in K_i\), \(x\) is uncolored (that is, \(x\notin \mathop{\mathrm{Dom}}(\phi)\)), and \[\big|\mathop{\mathrm{Dom}}(\phi) \cap N^+_D(x)\big| - \big|\phi\big(N^+_D(x)\big)\big| \geqslant d^+_D(x)-\Delta +b.\] We say that \(\phi\) is loosely \(i\)-extendable if there exist at least \(b\) distinct loose \(i\)-rescuers.

Similarly, a vertex \(x\) is a tight \(i\)-rescuer if \(x\in Y_i\), \(x\) is uncolored, and at least one of the following holds:

\(d^+_D(x) \leqslant\Delta\) and \(\big|\mathop{\mathrm{Dom}}(\phi) \cap N^+_D(x) \setminus U_i^\star\big| - \big|\phi\big(N^+_D(x) \setminus U_i^\star\big)\big| \geqslant d^+_D(x)-\Delta +b - \nu_i^\star\); or

\(d^-_D(x) \leqslant\Delta\) and \(\big|\mathop{\mathrm{Dom}}(\phi) \cap N^-_D(x) \setminus U_i^\star\big| - \big|\phi\big(N^-_D(x) \setminus U_i^\star\big)\big| \geqslant d^-_D(x)-\Delta +b-\nu_i^\star\). We further say that \(\phi\) is tightly \(i\)-extendable if there exist at least \(b\) tight \(i\)-rescuers.

We say that \(\phi\) is \(i\)-extendable if

\(D_i\) is loose and \(\phi\) is loosely \(i\)-extendable; or

\(D_i\) is tight and \(\phi\) is tightly \(i\)-extendable.

Finally, we say that \(\phi\) is extendable if it is \(s\)-extendable for every \(s\in S\) and \(i\)-extendable for every \(i\in [t]\). We conclude this section by showing that \(\phi\) cannot be extendable.

Claim 17. If \(\phi\) is extendable, then \(\vec{\chi}(D) \leqslant\Delta-b+1\).

Proof of claim. We show that \(\phi\) can be extended to \(D\). We first extend \(\phi\) to \(X_i\) for every \(i\in [t]\) as follows. Recall that \(\phi\) uses at most \(\lceil \Delta/2\rceil\) colors, which in particular implies that \(|\mathop{\mathrm{Dom}}(\phi) \cap X_i| \leqslant\frac{2}{3}\Delta\). Indeed, if this is not the case, then \[\tfrac{2}{3}\Delta < |\mathop{\mathrm{Dom}}(\phi) \cap X_i| \leqslant|\mathop{\mathrm{Dom}}(\phi)\cap K_i| + |U_i| \leqslant|\mathop{\mathrm{Dom}}(\phi)\cap K_i| + 4b,\] which implies that at least \(\frac{2}{3}\Delta - 4b > \lceil \frac{1}{2}\Delta\rceil\) vertices of \(K_i\) are colored by \(\phi\). In particular, two vertices of \(K_i\) are colored identically in \(\phi\). Since \(K_i\) is a biclique, this is a contradiction to \(\phi\) being a partial dicoloring.

Assume first that \(D_i\) is loose, so \(\phi\) is loosely \(i\)-extendable, and let \(\mathscr{L}\) be a set of \(b\) loose \(i\)-rescuers. We first extend the dicoloring to each vertex \(u\in U_i \setminus \mathop{\mathrm{Dom}}(\phi)\) by a color that is not appearing in \(N^+(u)\). This is possible as the number of colors appearing in \(N^+_D(u)\) is at most \[\begin{align} &|\mathop{\mathrm{Dom}}(\phi) \cap X_i| + |N^+_S(u) \setminus X_i| + |U_i|\\ &\leqslant\tfrac{2}{3}\Delta + d^+_D(u) - |N^+_D(u) \cap X_i| + |U_i|\\ &\leqslant(\tfrac{2}{3}+\varepsilon_b)\Delta +6b+1 &\text{by Claims~\ref{claim:degrees}, \ref{claim:dense95decomposition}\ref{claim:dense95decomposition:ii}, and~\ref{claim:matching95Di},}\\ &\leqslant\Delta-b &\text{by choice of \varepsilon_b and~\eqref{eq:largeDelta:3}.} \end{align}\] We then extend the coloring to \(K_i \setminus (\mathscr{L}\cup \mathop{\mathrm{Dom}}(\phi))\). This is possible because each of these vertices has in- or out-degree at most \(\Delta\), and at least \(b\) uncolored in- and out-neighbors, as \(\mathscr{L}\subseteq K_i\) and \(K_i\) is a biclique. Note that the vertices in \(\mathscr{L}\) are indeed uncolored by definition of loose \(i\)-rescuers. We can finally extend the coloring to each vertex \(y\in \mathscr{L}\) by choosing a color that is not used on \(N^+_D(y)\). To see that this is possible, note that \(y\) being a loose \(i\)-rescuer implies that there exists a set \(B \subseteq N^+_D(y)\) of \(d^+_D(y)-\Delta+b\) vertices whose colors in \(\phi\) appear in \(N^+_D(y) \setminus B\). Hence, the number of colors appearing in the out-neighborhood of \(y\) is at most \[d^+(y) - (d^+(y)-\Delta+b) = \Delta-b,\] as desired.

Assume now that \(D_i\) is tight, so \(\phi\) is tightly \(i\)-extendable, and let \(\mathscr{L}\) be a set of \(b\) tight \(i\)-rescuers. We proceed as above, but here we need to ensure that the vertices matched in \(M_i^\star\) receive the same color. Note that this is the case for the vertices of \(U_i^\star\) that are already colored, as by construction of \(\phi\), for every \(uv\in M_i^\star\), since \(u\) and \(v\) are identified in \(D^\star\), either \(\{u,v\} \cap \mathop{\mathrm{Dom}}(\phi) = \varnothing\) or \(\{u,v\} \subseteq \mathop{\mathrm{Dom}}(\phi)\) and \(\phi(u) = \phi(v)\). For every \(uv\in M_i^\star\) such that \(\{u,v\} \cap \mathop{\mathrm{Dom}}(\phi) =\varnothing\), we extend the dicoloring by giving to both \(u\) and \(v\) a color that is not appearing in \(N^+_D(u) \cup N^+_D(v)\). This is possible as the number of colors appearing in \(N^+_D(u)\cup N^+_D(v)\) is at most \[\begin{align} |\mathop{\mathrm{Dom}}(\phi) \cap X_i| + |N^+_D(u) \setminus X_i|+ |N^+_D(v) \setminus X_i| + |U_i^\star| \leqslant(\tfrac{2}{3}+2\varepsilon_b)\Delta +8b+2 \leqslant\Delta-b. \end{align}\] by 3 . We then extend the dicoloring to \(R_i \setminus \mathop{\mathrm{Dom}}(\phi)\), which is possible as the number of colors appearing in \(N^+(r)\) is at most \[\begin{align} |\mathop{\mathrm{Dom}}(\phi) \cap X_i| + |N^+(r) \setminus X_i|+ |U_i^\star| + |R_i| \leqslant(\tfrac{2}{3}+\varepsilon_b)\Delta +10b +1\leqslant\Delta-b \end{align}\] by 3 . We then extend the coloring to \(K_i^\star \setminus (\mathscr{L}\cup \mathop{\mathrm{Dom}}(\phi))\), which is again possible because each of these vertices has \(b\) uncolored out- and in-neighbors as \(K_i^\star\) is a biclique. We finally extend the coloring to each vertex \(y\in \mathscr{L}\). To see that this is possible, recall that, by definition of being a tight \(i\)-rescuer, \(y\in Y_i\) and that, by Claim 14, \(U_i^\star \subseteq N^\pm_D(y)\). Note also that, as \(y\) is a tight \(i\)-rescuer, at most \(\Delta-b+\nu_i^\star\) colors appear in both \(N^+_D(y) \setminus U_i^\star\) and \(N^-_D(y) \setminus U_i^\star\). By construction of the current partial dicoloring, we finally obtain that the maximum number of colors appearing in \(N^+_D(y)\) and \(N^-_D(y)\) is at most \[(\Delta-b+\nu_i^\star)-\tfrac{1}{2}|U_i^\star| = \Delta-b,\] as desired.

We finally extend \(\phi\) to \(S\) by choosing for every vertex \(s\in S\) a color that is not appearing in \(N^+_D(s)\). Let us justify that such a color is available. First, if \(|M^\star \cap \binom{N^+_D(s)}{2}| \geqslant 2b+1\), then since we explicitly gave the same color to the vertices matched in \(M^\star\), the number of colors used on \(N^+_D(s)\) is at most \(d^+_D(s) - (2b+1) \leqslant\Delta-b\) by Claim 7, as desired. Otherwise, if \(|M^\star \cap \binom{N^+_D(s)}{2}| < 2b+1\), note that by definition of \(\phi\) being \(s\)-extendable, there exists a set \(B_s \subseteq N^+_D(s)\) of \(2b+1\) vertices whose colors in \(\phi\) appear in \(N^+_D(s) \setminus B_s\). Hence, the number of colors appearing in the out-neighborhood of \(s\) is again at most \(d^+_D(s) - (2b+1) \leqslant\Delta-b\). ◻

4.5 The probabilistic analysis↩︎

Our final goal is to prove that \[\mathbb{P}(\phi \text{ is extendable}) >0,\] which together with Claim 17 implies that \(\vec{\chi}(D) \leqslant\Delta-b+1\), a contradiction. To prove this, we show that, for every \(s\in S\), \(\phi\) is likely to be \(s\)-extendable, and that for every \(i\in [t]\), \(\phi\) is likely to be \(i\)-extendable. We finally conclude that \(\phi\) is extendable with positive probability using Lovász Local Lemma.

We make use of the following observation, intuitively saying that the maximum degree in \(D^\star\) is still close to \(\Delta\).

Claim 18. Every vertex \(x\in V(D^\star)\) satisfies \(d^+_{D^\star}(x) \leqslant\Delta+31b\) and \(d^-_{D^\star}(x) \leqslant\Delta+31b\).

Proof of claim. If \(x\in V(D^\star)\cap V(D)\), then this is an immediate consequence of Claim 7, as then identifying vertices cannot increase the degree of \(x\). Assume thus that \(x=x_{u,v}\) corresponds to the identification of \(\{u,v\} \in M^\star\). Recall that, by definition of \(M^\star\), there exists some \(i\in \mathcal{I}\) such that \(\{u,v\} \in M_i^\star\) (recall that \(\mathcal{I}\) denotes the set of integers \(i\) such that \(D_i\) is tight). Therefore, we have \[\begin{align} d^+_{D^\star}(x) &\leqslant d^+_{D}(v) + |N^+_D(u)\setminus N^+_D(v)|\\ &\leqslant d^+_D(v) + d^+_D(u) - |N^\pm_D(u) \cap N^\pm_D(v)|\\ &\leqslant 2(\Delta+b+1) - |N^\pm_D(u) \cap N^\pm_D(v)| &\text{by Claim~\ref{claim:degrees},}\\ &\leqslant\Delta+31b &\text{by Claim~\ref{claim:adjacency95Uis95bis}}, \end{align}\] and similarly \(d^-_{D^\star}(x) \leqslant\Delta+31b\), as desired. ◻

4.5.1 Probabilistic analysis: the sparse vertices↩︎

We first prove that, for every \(s\in S\), \(\phi\) is likely to be \(s\)-extendable. We make use of the following observation, which intuitively says that the vertices in \(S\) remain sparse in \(D^\star\). Note that \(S\) is not spanned by \(M^\star\) by construction, so indeed \(S\subseteq V(D^\star)\).

Claim 19. For every vertex \(s\in S\), the digraph \(D^\star[N^+_{D^\star}(s)]\) contains at most \(\Delta^2 - \frac{1}{3}d\Delta\) arcs.

Proof of claim. Let \(m(s)\) and \(m^\star(s)\) denote the number of arcs in \(D[N^+_D(s)]\) and \(D^\star[N^+_{D^\star}(s)]\) respectively. Recall that \(\Delta_{\rm m}\) denotes \(\Delta_{\max}(D)\). By Claim 8 [claim:dense95decomposition:iv] and by definition of being \(d/2\)-sparse, we have \[m(s) \leqslant\Delta_{\rm m}(\Delta_{\rm m}-1) - \tfrac{1}{2}d\Delta_{\rm m}.\]

Observe first that identifying two vertices in \(N^+_D(s)\) or two vertices in \(V(D)\setminus (N^+_D(s)\cup \{s\})\) does not increase the number of arcs induced by the out-neighborhood of \(s\). Let \(u_1v_1,\dots,u_rv_r\) be the edges of \(M^\star\) with exactly one extremity in \(N^+_D(s)\). Assume without loss of generality that \(u_j \in N^+_D(s)\) and \(v_j \notin N^+_D(s)\) for every \(j\in [r]\).

Next, observe that if some arc \(a\) belongs to \(D^\star[N^+_{D^\star}(s)]\) but not to \(D[N^+_D(s)]\), necessarily there is some \(j\in [r]\) such that \(a\) is incident to \(v_j\) but not to \(u_j\) in \(D\). Recall that \(u_jv_j \in M_i^\star\) for some \(i\) such that \(D_i\) is tight. Therefore, \[\begin{align} m^\star(s) &\leqslant m(s) + \sum_{j\in [r]} \Big(\big|N^+_{D}(v_j) \setminus N^+_D(u_j)\big| + \big|N^-_{D}(v_j) \setminus N^-_D(u_j)\big|\Big)\\ &\leqslant m(s) + \sum_{j\in [r]}\Big( d^+_D(v_j) +d^-_D(v_j) - 2|N^\pm_D(u_j) \cap N^\pm_D(v_j)| \Big)\\ &\leqslant m(s) + 60b\cdot r &\text{by Claims~\ref{claim:degrees} and~\ref{claim:adjacency95Uis95bis},}\\ &\leqslant m(s) + 60b\cdot \Delta_{\rm m}\\ &\leqslant\Delta_{\rm m}(\Delta_{\rm m}-1) - (\tfrac{1}{2}d-60b)\Delta_{\rm m}\\ &\leqslant(\Delta+b+1)(\Delta+b) - (\tfrac{1}{2}d-60b)(\Delta-b) &\text{by Claim~\ref{claim:degrees},} \\ &\leqslant\Delta^2 - \tfrac{1}{3}d\Delta &\text{by~\eqref{eq:largeDelta:5},} \end{align}\] as desired. ◻

Claim 20. For every vertex \(s\in S\), \(\mathbb{P}(\text{\phi is not s-extendable})\leqslant\exp(-\log^2(\Delta))\).

Proof of claim. Let us fix a vertex \(s\in S\). Let \(M_s\) be the edges of \(M^\star\) included in \(N^+_D(s)\), that is \(M_s = M^\star \cap \binom{N^+(s)}{2}\). We assume that \(|M_s| \leqslant 2b\), for otherwise \(\phi\) must be \(s\)-extendable by definition (that is, \(\mathbb{P}(\text{\phi is s-extendable}) = 1\)). In particular, we have \[\label{eq:mindeg95sparse} d^+_{D^\star}(s) \geqslant d^+_{D}(s) - 2b \geqslant\Delta-3b+1.\tag{10}\] by Claim 7. For the sake of better readability, in the following let us denote by \(N_s\) the set of out-neighbors of \(s\) in \(D^\star\). Let \(Z_s\) denote the number of colors \(c\in [\lceil\Delta/2\rceil]\) such that \(c\) is used and retained by exactly two vertices in \(N_s\), and not used by any other vertex in \(N_s\). Formally, \(Z_s\) is the number of colors \(c\in [\lceil \Delta/2\rceil ]\) for which there exists distinct vertices \(x,y\in N_s\) such that:

\(\phi'(x) = \phi'(y) = c\),

\(\phi'(z) \neq c\) for every \(z\in N_s \setminus \{x,y\}\), and

\(\{x,y\} \subseteq \mathop{\mathrm{Dom}}(\phi^\star)\). Observe that \[|\mathop{\mathrm{Dom}}(\phi) \cap N^+_D(s) | - |\phi(N^+_D(s))| \geqslant|\mathop{\mathrm{Dom}}(\phi^\star) \cap N^+_{D^\star}(s) | - |\phi(N^+_{D^\star}(s))|\geqslant Z_s,\] which implies that \[\mathbb{P}(\text{\phi is s-extendable}) \geqslant\mathbb{P}(Z_s\geqslant 2b+1) = \mathbb{P}(Z_s> 2b).\] We bound the latter term by first proving that the expectation of \(Z_s\) is large and then that \(Z_s\) is concentrated around its expectation. Let \(\mathscr{B}_s\) be the set of pairs \(\{u,v\} \subseteq N_s\) such that \(D^\star\) contains at most one arc between \(u\) and \(v\).

Subclaim 1. We have \(\mathbb{E}(Z_s) \geqslant\frac{1}{2^{17}\Delta}|\mathscr{B}_s|\).

Proof of subclaim. For every pair of vertices \(\{x,y\} \in \mathscr{B}_s\) and every color \(c\in [\lceil\Delta/2\rceil]\), we let \(A_{\{x,y\},c}\) be the event that \(x,y\) are the unique vertices colored \(c\) in \(N_s\) and that they both retain their color. We let \(Z_{\{x,y\},c}\) be the binary random variable equals to \(1\) if \(A_{\{x,y\},c}\) holds and \(0\) otherwise. By definition, we have \[Z_s = \sum_{\substack{\{x,y\}\in \mathscr{B}_s,\\c\in [\lceil\Delta/2\rceil]}} Z_{\{x,y\},c}.\] Note that \(A_{\{x,y\},c}\) holds in particular if \(\phi'(x) = \phi'(y) = c\) and \(\phi'(w)\neq c\) for every \(w\in (N_s \cup N^+_{D^\star}(x)\cup N^+_{D^\star}(y))\setminus \{x,y\}\). Therefore, using that \(\frac{\Delta}{2}\leqslant\lceil \frac{\Delta}{2}\rceil \leqslant\Delta\) we have \[\begin{align} \mathbb{E}(Z_{\{x,y\},c}) = \mathbb{P}(A_{\{x,y\},c}) &\geqslant\left(\frac{1}{\Delta}\right)^2\cdot \left(1-\frac{2}{\Delta}\right)^{3\Delta+93b} &\text{by Claim~\ref{claim:degrees95Ds},}\\ &\geqslant\frac{1}{\Delta^2}\cdot \left(1-\frac{2}{\Delta}\right)^{4\Delta} &\text{by~\eqref{eq:largeDelta:3},}\\ &\geqslant\frac{1}{2^{16}\Delta^2}&\text{by~\eqref{eq:largeDelta:6}.} \end{align}\] By linearity of the expectation, it follows that \[\mathbb{E}(Z_s) \geqslant\frac{\Delta}{2}\cdot |\mathscr{B}_s| \cdot \frac{1}{2^{16}\Delta^2} = \frac{|\mathscr{B}_s|}{2^{17}\Delta},\] as desired. ◻

Subclaim 2. For any real number \(\lambda> 714\sqrt{|\mathscr{B}_s|/\Delta} + 2752\), we have \[\mathbb{P}(|Z_s-\mathbb{E}(Z_s)|>\lambda)\leqslant 8\exp\left(\frac{-\lambda^2\Delta}{1024|\mathscr{B}_s| + 256\lambda\Delta}\right).\]

Proof of subclaim. We consider two auxiliary random variables. Let \(Z_s^{{\rm add}}\) be the number of colors \(c\) such that, for some \(\{x,y\} \in \mathscr{B}_s\), \(\phi'(x) = \phi'(y) =c\). Let \(Z_s^{{\rm del}}\) be the number of colors \(c\) such that, for some \(\{x,y\} \in \mathscr{B}_s\), \(\phi'(x) = \phi'(y)=c\) and

\(c\) is not retain by at least one of \(\{x,y\}\), that is \(\{x,y\} \nsubseteq \mathop{\mathrm{Dom}}(\phi^\star)\); or

there exists \(z\in N_s\setminus \{x,y\}\) such that \(\phi'(z) =c\). Observe that \(Z_s = Z_s^{{\rm add}}- Z_s^{{\rm del}}\). We show that these auxiliary random variables are concentrated, and then deduce that \(Z_s\) is concentrated as well.

Given \(\{x,y\}\in \mathscr{B}_s\) and a color \(c\in[\lceil\Delta/2\rceil]\), let \(A^{{\rm add}}_{\{x,y\},c}\) be the event that \(x\) and \(y\) are assigned color \(c\), and let \(Z^{{\rm add}}_{\{x,y\},c}\) be the random variable equal to \(1\) if \(A^{{\rm add}}_{\{x,y\},c}\) holds, and \(0\) otherwise. We have that \[Z_s^{{\rm add}}\leqslant\sum_{\substack{\{x,y\}\in \mathscr{B}_s,\\c\in [\lceil \Delta/2\rceil]}} Z^{{\rm add}}_{\{x,y\},c}.\] Therefore, by linearity of the expectation, \[\label{eq:EM9442} \mathbb{E}(Z_s^{{\rm add}}) \leqslant\sum_{\substack{\{x,y\}\in \mathscr{B}_s,\\c\in [\lceil \Delta/2\rceil]}} \mathbb{P}(A^{{\rm add}}_{\{x,y\},c}) = \lceil\Delta/2\rceil \cdot |\mathscr{B}_s| \cdot \left(\frac{1}{\lceil\Delta/2\rceil}\right)^2 \leqslant\frac{2}{\Delta}\cdot |\mathscr{B}_s|.\tag{11}\]

We note that changing the outcome of any color assignment affects \(Z_s^{{\rm add}}\) by at most \(1\). Moreover, whenever \(Z_s^{{\rm add}}\geqslant k\) for some integer \(k\), this can be certified by revealing at most \(2k\) color assignments: for each color \(c\) counted by \(Z_s^{{\rm add}}\), it suffices to exhibit two vertices \(x\) and \(y\) with \(\{x,y\}\in \mathscr{B}_s\) and \(\phi'(x) = \phi'(y)=c\). Therefore, by Lemma 5 together with 11 , we get \[\label{eq:M9442} \mathbb{P}(|Z_s^{{\rm add}}- \mathbb{E}(Z_s^{{\rm add}})|>\lambda)\leqslant 4\exp\left(\frac{-\lambda^2 \Delta}{128|\mathscr{B}_s|+64\lambda\Delta}\right)\tag{12}\] for any real number \(\lambda > 252\sqrt{|\mathscr{B}_s|/\Delta}+688\).

Similarly, \(Z_s^{{\rm del}}\) is affected by at most \(1\) when the outcome of any color assignment is changed. Moreover, whenever \(Z_s^{{\rm del}}\geqslant k\), this can be certified by revealing at most \(4k\) color assignments: for each one of the \(k\) colors, it suffices to exhibit two vertices \(x\) and \(y\) with \(\{x,y\}\in \mathscr{B}_s\), and either

one in-neighbor \(x^-\) and one out-neighbor \(x^+\) of \(x\), or

a vertex \(z \in N_s \setminus \{x,y\}\), such that all such vertices have been assigned that color. By Lemma 5, 11 , and the fact that \(Z_s^{{\rm del}}\leqslant Z_s^{{\rm add}}\) by definition, we have \[\label{eq:M94del} \mathbb{P}(|Z_s^{{\rm del}}-\mathbb{E}(Z_s^{{\rm del}})|>\lambda)\leqslant 4\exp\left(\frac{-\lambda^2 \Delta}{256|\mathscr{B}_s|+128\lambda\Delta}\right)\tag{13}\] for any \(\lambda> 357\sqrt{|\mathscr{B}_s|/\Delta} + 1376\). Recall that \(Z_s = Z_s^{{\rm add}}-Z_s^{{\rm del}}\), hence by 12 and 13 we obtain \[\begin{align} \mathbb{P}(|Z_s-\mathbb{E}(Z_s)|>\lambda) &\leqslant\mathbb{P}\left(|Z_s^{{\rm add}}-\mathbb{E}(Z_s^{{\rm add}})|>\tfrac{\lambda}{2}\right) +\mathbb{P}\left(|Z_s^{{\rm del}}-\mathbb{E}(Z_s^{{\rm del}})|>\tfrac{\lambda}{2}\right) \\ &\leqslant 8\exp\left(\frac{-\lambda^2\Delta}{1024|\mathscr{B}_s| + 256\lambda\Delta}\right) \end{align}\] for any \(\lambda> 714\sqrt{|\mathscr{B}_s|/\Delta} + 2752\). The subclaim follows. ◻

To make use of Subclaims 1 and 2, we need to estimate \(|\mathscr{B}_s|\). For this, let \(m_s\) denote the number of arcs in \(D^\star[N_s]\). Since there are at most two arcs between any two vertices, we have \[\begin{align} |\mathscr{B}_s| &\geqslant\textstyle \binom{d^+_{D^\star}(s)}{2} - \tfrac{1}{2} m_s \\ &\geqslant\tfrac{1}{2}(\Delta-3b)^2 - \tfrac{1}{2}m_s &\text{by~\eqref{eq:mindeg95sparse},}\\ &\geqslant\tfrac{1}{2}(\Delta-3b)^2 - \tfrac{1}{2}\Delta^2 + \tfrac{1}{6}d\Delta &\text{by Claim~\ref{claim:preserve95sparseness},}\\ &= \tfrac{1}{6}d\Delta - 3b\Delta + \tfrac{9}{2}b^2\\ &\geqslant\tfrac{1}{8}d\Delta &\text{by~\eqref{eq:largeDelta:5}.} \end{align}\] Together with Subclaim 1, we thus obtain \(\mathbb{E}(Z_s) \geqslant\frac{1}{2^{20}}d\). In particular, \(\frac{1}{2}\mathbb{E}(Z_s) \geqslant 2b+1\) by 4 , which implies that \[\mathbb{P}(Z_s < 2b+1) \leqslant\mathbb{P}(|Z_s - \mathbb{E}(Z_s)| > \tfrac{1}{2}\mathbb{E}(Z_s)).\] Let thus \(\lambda = \tfrac{1}{2}\mathbb{E}(Z_s)\). Note that, by 5 , together with the fact that \(|\mathscr{B}_s| \geqslant\frac{1}{8}d\Delta\), we have \[2^{-16} \cdot\sqrt{|\mathscr{B}_s|} \geqslant 715\sqrt{\Delta}.\] By multiplying each side of the inequality by \(\sqrt{|\mathscr{B}_s|}/\Delta\), we get that \[\begin{align} \lambda \geqslant 2^{-16} \cdot \frac{|\mathscr{B}_s|}{\Delta} &\geqslant 715\cdot \sqrt{\frac{|\mathscr{B}_s|}{\Delta}} \geqslant 714\cdot \sqrt{\frac{|\mathscr{B}_s|}{\Delta}} + \sqrt{d/8} > 714\cdot \sqrt{\frac{|\mathscr{B}_s|}{\Delta}} +2752, \end{align}\] where the last inequality follows from 5 . Therefore, Subclaim 2 can be applied with \(\lambda = \frac{1}{2}\mathbb{E}(Z_s)\), and we have \[\begin{align} \mathbb{P}(\text{\phi is not s-extendable}) &\leqslant\mathbb{P}(Z_s<2b+1)\\ &\leqslant\mathbb{P}(|Z_s-\mathbb{E}(Z_s)| > \lambda)\\ &\leqslant 8\exp\left(\frac{-\lambda\Delta}{1024\frac{|\mathscr{B}_s|}{\lambda} + 256\Delta}\right) &\text{by Subclaim~\ref{subclaim:sparse952},}\\ &\leqslant 8\exp\left(\frac{-|\mathscr{B}_s|}{2^{46}\Delta+ 2^{26}\Delta}\right) &\text{by Subclaim~\ref{subclaim:sparse951},}\\ &\leqslant 8\exp\left(-2^{-50}d\right) &\text{as |\mathscr{B}_s|\geqslant\tfrac{1}{8}d\Delta,}\\ &\leqslant\exp({-\log^2(\Delta)}) &\text{by~\eqref{eq:largeDelta:8}.} \end{align}\] The claim follows. ◻

4.5.2 Probabilistic analysis: the dense sets↩︎

We now prove that, for every \(i\in [t]\), \(\phi\) is likely to be \(i\)-extendable.

Claim 21. For every integer \(i\in [t]\), \(\mathbb{P}(\text{\phi is not i-extendable}) \leqslant\exp(- \log^2(\Delta))\).

Proof of claim. Let us fix \(i\in [t]\). To prove the claim, we only have to prove that, with high probability, there exist at least \(b\) loose \(i\)-rescuers (if \(D_i\) is loose) or at least \(b\) tight \(i\)-rescuers (if \(D_i\) is tight). We first show that the expected number of \(i\)-rescuers is large, and then that this number is concentrated, hence showing that the number of \(i\)-rescuers is likely to be at least \(b\).

In order to avoid duplicating arguments between the loose and tight cases, let us provide a few more definitions. First, if \(D_i\) is loose, we let \(K\) be \(K_i\), otherwise we let \(K\) be \(K_i^\star\). Next, if \(D_i\) is loose, let \(\mathcal{Y}\) be the set of loose \(i\)-saviors, otherwise let \(\mathcal{Y}\) be the set of tight \(i\)-saviors.

Note that, in either case, \(\mathcal{Y} \subseteq V(D) \cap V(D^\star)\), that is, the vertices in \(\mathcal{Y}\) are not identified with another vertex when constructing \(D^\star\). Indeed, if some \(y\in \mathcal{Y}\) is identified with another vertex, it means that \(y\) is spanned by \(M^\star\). By definition, this happens only if \(i\in \mathcal{I}\) and \(y\in U_i^\star\). This is a contradiction, as if \(i\in \mathcal{I}\), then \(y\) is a tight \(i\)-savior, and by definition \(y\in Y_i\).

Finally, for every \(y\in \mathcal{Y}\), let \[\mathscr{Z}_y' = \begin{cases} N^+_D(y) \cap \mathscr{Z}_i &\text{if D_i is loose,}\\ N^+_D(y) \cap \mathscr{Z}_i &\text{if D_i is tight and y is a tight i^+-savior,}\\ N^-_D(y) \cap \mathscr{Z}_i &\text{if D_i is tight and y is a tight i^--savior.} \end{cases}\] Further, for every \(y\in \mathcal{Y}\), let \(\mathscr{Z}_y\) be an arbitrary subset of \(\mathscr{Z}_y'\) of size exactly \[\begin{cases} d^+(y)-\Delta+b & \text{if D_i is loose,}\\ d^+(y) - \Delta+b - \nu_i^\star &\text{if D_i is tight and y is a tight i^+-savior,}\\ d^-(y)-\Delta+b- \nu_i^\star &\text{if D_i is tight and y is a tight i^--savior.} \end{cases}\] The existence of \(\mathscr{Z}_y\) is guaranteed by the definition of \(y\) being a loose or tight \(i\)-savior. In particular, note that \(|\mathscr{Z}_y|\leqslant 2b+1\). Finally, for every \(y\in \mathcal{Y}\), we let \(\mathscr{Z}^\star_y\) be the set of vertices corresponding to \(\mathscr{Z}_y\) in \(D^\star\), that is \[\begin{align} \mathscr{Z}_y^\star =~ &\{z \in \mathscr{Z}_y : \text{z is not spanned by M^\star}\}\cup \{x_{z,u} : z\in \mathscr{Z}_y \text{ and z is matched to u in M^\star}\}. \end{align}\]

Recall that, by definition, the vertices in \(\mathscr{Z}_i\) can have only a few neighbors (namely, less than \(2\log^4(\Delta))\)) in \(X_i\). It follows that we can extract a large set \(\mathcal{Y}' \subseteq \mathcal{Y}\) for which the sets \((\mathscr{Z}_{y}^\star\cup \{y\})_{y\in \mathcal{Y}'}\) are pairwise disjoint.

Subclaim 3. There exists \(\mathcal{Y}' \subseteq \mathcal{Y}\) such that \(|\mathcal{Y}'| \geqslant\frac{\Delta}{24b \cdot \log^4(\Delta)}\) and the sets \((\mathscr{Z}_{y}^\star\cup \{y\})_{y\in \mathcal{Y}'}\) are pairwise disjoint.

Proof of subclaim. Let \(\mathcal{Y}'\subseteq \mathcal{Y}\) be a set for which the sets \((\mathscr{Z}_{y}^\star\cup \{y\})_{y\in \mathcal{Y}'}\) are pairwise disjoint and, with respect to this property, has maximum cardinality. Let \(\mathscr{Z}\) be the set of vertices \(z\in \mathscr{Z}_i\) such that either

\(z\in \mathscr{Z}_y\) for some \(y\in \mathcal{Y}'\), or

\(z\) is matched to a vertex \(z^\star\) in \(M^\star\) and \(z^\star\in \mathscr{Z}_y\) for some \(y\in \mathcal{Y}'\). By maximality of \(\mathcal{Y}'\), in \(D\), every vertex \(y_1\in \mathcal{Y}\setminus \mathcal{Y}'\) has a neighbor \(z_1\in \mathscr{Z}\). Moreover, every vertex in \(\mathcal{Y}'\) has a neighbor in \(\mathscr{Z}\) by definition. It follows that \[\sum_{z\in \mathscr{Z}} |N_D(z)\cap X_i| \geqslant|\mathcal{Y}|.\] Moreover, since \(\mathscr{Z}\subseteq \mathscr{Z}_i\), and by definition the vertices in \(\mathscr{Z}_i\) have less than \(2\log^4(\Delta)\) neighbors inside \(X_i\) in \(D\). Therefore, \[|\mathscr{Z}| \geqslant\frac{|\mathcal{Y}|}{2\log^4(\Delta)}.\] By definition, note that at least half of the vertices in \(\mathscr{Z}\) belong to \(\mathscr{Z}_y\) for some \(y\in \mathcal{Y}'\). Therefore, it follows that \[\sum_{y\in \mathcal{Y}'} |\mathscr{Z}_y| \geqslant\frac{1}{2}|\mathscr{Z}|\geqslant\frac{|\mathcal{Y}|}{4\log^4(\Delta)}.\] Finally, by definition, for every \(y\in \mathcal{Y}\) we have \(|\mathscr{Z}_y|\leqslant 2b+1\). It follows that \[|\mathcal{Y}'|\cdot (2b+1)\cdot 4\log^4(\Delta) \geqslant|\mathcal{Y}|.\] Recall that, by Claims 12 and 16, there exist at least \(\tfrac{1}{2}\Delta\) loose \(i\)-saviors if \(D_i\) is loose, and at least \(\tfrac{1}{2}\Delta\) tight \(i\)-saviors if \(D_i\) is tight. Therefore, \(|\mathcal{Y}| \geqslant\tfrac{1}{2}\Delta\), and it follows from the inequality above that \[|\mathcal{Y}'| \cdot 24b \cdot \log^4(\Delta) \geqslant\Delta.\] The subclaim follows. ◻

Henceforth, let us thus fix \(\mathcal{Y}' \subseteq \mathcal{Y}\) a subset of \(\mathcal{Y}\) of cardinality precisely \(\lceil \frac{\Delta}{24b \cdot \log^4(\Delta)}\rceil\), with the property that the sets \((\mathscr{Z}_{y}^\star\cup \{y\})_{y\in \mathcal{Y}'}\) are pairwise disjoint. Let \(\mathcal{T}=\bigcup_{y\in \mathcal{Y}'}(\mathscr{Z}_{y}^\star\cup \{y\})\) be the set of vertices spanned by these. We finally let \(T\) be the random variable counting the number of vertices \(y\in\mathcal{Y}'\) such that:

\(y\notin \mathop{\mathrm{Dom}}(\phi^\star)\);

\(\mathscr{Z}_{y}^\star \subseteq \mathop{\mathrm{Dom}}(\phi^\star)\);

for every \(z\in \mathscr{Z}_y^\star\), there exists \(x\in K\) such that \(x\in \mathop{\mathrm{Dom}}(\phi^\star)\) and \(\phi'(z) = \phi'(x)\); and

for every vertex \(z\in \mathscr{Z}_y^\star\) and every \(u\in \mathcal{T}\setminus \{z\}\), \(\phi'(z) \neq \phi'(u)\).

The key point here is that \(T\) is a lower bound on the number of rescuers. The reader may note that condition [enum:good95triple954] is not necessary for this, but we need it later in order to apply Azuma’s inequality.

Subclaim 4. If \(D_i\) is loose, then there exist at least \(T\) loose \(i\)-rescuers. If \(D_i\) is tight, then there exist at least \(T\) tight \(i\)-rescuers.

Proof of subclaim. Let us fix an arbitrary vertex \(y\in \mathcal{Y}'\) such that \(y\) satisfies conditions [enum:good95triple951] to [enum:good95triple954], and let us show that \(y\) is a loose (resp. tight) \(i\)-rescuer if \(D_i\) is loose (resp. tight). Observe first that, by [enum:good95triple951], \(y\) is uncolored. Moreover, note that \(y\in K\), since the vertices in \(\mathcal{Y}\) are, by definition, loose (resp.tight) \(i\)-saviors, and every such vertex belongs to \(K\). Then, note that, by conditions [enum:good95triple952] and [enum:good95triple953], \(\phi(\mathscr{Z}_y) \subseteq \phi(K)\). If \(D_i\) is loose, it then follows that \[|\mathop{\mathrm{Dom}}(\phi) \cap N^+_D(y)| - |\phi(N^+_D(y))| \geqslant|\mathscr{Z}_y| = d^+_D(y)-\Delta+b,\] hence showing that \(y\) is a loose \(i\)-rescuer. Similarly, if \(D_i\) is tight and \(y\) is a tight \(i^+\)-savior, then \(d^+(y)\leqslant\Delta\) and, since \(K\cup \mathscr{Z}_y\) is disjoint from \(U_i^\star\), \[|\mathop{\mathrm{Dom}}(\phi) \cap N^+_D(y) \setminus U_i^\star|- |\phi(N^+_D(x) \setminus U_i^\star)| \geqslant d^+(y)-\Delta+b-\nu_i^\star,\] hence implying that \(y\) is a tight \(i\)-rescuer. Finally, in the remaining case, that is \(D_i\) is tight and \(y\) is a tight \(i^-\)-savior, then \(d^-(y)\leqslant\Delta\) and \[|\mathop{\mathrm{Dom}}(\phi) \cap N^-(y) \setminus U_i^\star| - |\phi(N^-_D(x) \setminus U_i^\star)| \geqslant d^-(y)-\Delta+b-\nu_i^\star,\] again implying that \(y\) is a tight \(i\)-rescuer. ◻

It remains to show that \(T\) is at least \(b\) with probability at least \(\exp(-\log^2(\Delta))\), and the claim then follows from Subclaim 4. As announced, we first prove that the expectation of \(T\) is large, and then that it is concentrated. To show that \(\mathbb{E}(T)\) is large, we need a large set of vertices that will be candidates for being the vertices \(x\in K\) of condition [enum:good95triple953]. For this, we let \[\mathcal{K}= K \setminus \bigcup_{z\in \mathcal{T}\setminus \mathcal{Y}'} N_{D^\star}(z).\] Note that both \(\mathcal{Y}'\) and \(\mathcal{K}\) are included in \(K\), so vertices in \(\mathcal{Y}'\) and \(\mathcal{K}\) are linked with digons. Note also that \(\mathcal{Y}' \cap \mathcal{K}= \varnothing\) by definition. Moreover, since the vertices in \(\mathscr{Z}_i\) have at most \(2\log^4(\Delta)\) neighbors in \(X_i\), we have \[\begin{align} |\mathcal{K}| &\geqslant|K| - \sum_{y\in \mathcal{Y}'} \sum_{z\in \mathscr{Z}_y} |N_D(z) \cap X_i|\\ &\geqslant|K| - |\mathcal{Y}'| \cdot (2b+1) \cdot 2\log^4(\Delta) &\text{by definition of \mathscr{Z}_y,}\\ &\geqslant|K| - \tfrac{1}{4}\Delta &\text{by definition of \mathcal{Y}',}\\ &\geqslant\tfrac{3}{4}\Delta-\tfrac{4}{\varepsilon_b}d-8b &\text{by Claim~\ref{claim:size95K},}\\ &\geqslant\tfrac{1}{2}\Delta &\text{by~\eqref{eq:largeDelta:3}.} \end{align}\] We are now ready to estimate the expectation of \(T\).

Subclaim 5. \(\mathbb{E}(T)\geqslant\Delta^{2/3} + b\).

Proof of subclaim. For every vertex \(y\in \mathcal{Y}\), we let \(\ell(y) = |\mathscr{Z}_y^\star|\) and fix an arbitrary ordering \((z_1^y,\dots,z_{\ell(y)}^y)\) of \(\mathscr{Z}_y^\star\). Given:

a vertex \(y\in \mathcal{Y}'\),

\(\ell(y)+1\) distinct vertices \(\mathcal{X}=(x_0,x_1,\dots,x_{\ell(y)})\) of \(\mathcal{K}\), and

\(\ell(y)+1\) distinct colors \(\mathcal{C}= (c_0,c_1,\dots,c_{\ell(y)})\) of \([\lceil\Delta/2\rceil]\), we let \(A_{y,\mathcal{X},\mathcal{C}}\) be the event that

\(\phi'(y) = \phi'(x_0) = c_0\) and \(\phi'(u) \neq c_0\) for every other vertex \(u\) in \(\mathcal{K}\cup \mathcal{T}\); and

for every \(1\leqslant j \leqslant\ell(y)\), \(\phi'(z_j^y) = \phi'(x_j) = c_j\), and \(\phi'(u)\neq c_j\) for every other vertex \(u\) in \(\mathcal{K}\cup \mathcal{T}\cup N^+_{D^\star}(z_j^y)\cup N^+_{D^\star}(x_j)\). Since \(\{yx_0,x_0y\}\) is a digon, observe that \(y\) must be counted by \(T\) when \(A_{y,\mathcal{X},\mathcal{C}}\) holds. Since, in \(D^\star\), every vertex has out-degree at most \(\Delta+31b\) by Claim 18, we have \[\mathbb{P}(A_{y,\mathcal{X},\mathcal{C}}) \geqslant\left(\frac{1}{\Delta}\right)^{2\ell(y)+2} \cdot \left(1-(\ell(y)+1)\cdot \frac{2}{\Delta}\right)^{|\mathcal{K}|+|\mathcal{T}|+\ell(y)\cdot (\Delta+31b)}.\] Recall that \(\ell(y) \leqslant 2b+1\). Therefore, using that \(|\mathcal{K}| \leqslant\Delta\) (as \(\mathcal{K}\) is a biclique), that \[|\mathcal{T}| \leqslant(2b+1) \cdot |\mathcal{Y}| \leqslant\Delta / 8\log^4(\Delta) \leqslant\Delta,\] and that \(\Delta+31b \leqslant 2\Delta\), we obtain that \[\mathbb{P}(A_{y,\mathcal{X},\mathcal{C}}) \geqslant\left(\frac{1}{\Delta}\right)^{2\ell(y)+2} \cdot \left(1- \frac{6b}{\Delta}\right)^{8b\cdot \Delta}\geqslant\left(\frac{1}{\Delta}\right)^{2\ell(y)+2} \cdot \frac{1}{2^{96b^2}}\] by 6 . For every \(y\in \mathcal{Y}'\), since \(|\mathcal{K}| \geqslant\tfrac{1}{2}\Delta\), note that we have at least \[\tfrac{1}{2}\Delta \cdot (\tfrac{1}{2}\Delta-1) \cdot \ldots \cdot (\tfrac{1}{2}\Delta-\ell(y)) \geqslant(\tfrac{1}{4}\Delta)^{\ell(y)+1}\] choices for \(\mathcal{X}\), and at least \[\tfrac{1}{2}\Delta \cdot (\tfrac{1}{2}\Delta-1) \cdot \ldots \cdot (\tfrac{1}{2}\Delta-\ell(y)) \geqslant(\tfrac{1}{4}\Delta)^{\ell(y)+1}\] choices for \(\mathcal{C}\), where in both cases we use that \(\frac{1}{2}\Delta-\ell(y) \geqslant\frac{1}{2}\Delta-2b-1 \geqslant\frac{1}{4}\Delta\) by 3 . For every \(y\in \mathcal{Y}'\), let \(A_y\) be the even that \(y\) is counted by \(T\). For every fixed \(y\in\mathcal{Y}'\), since the events of the form \(A_{y,\mathcal{X},\mathcal{C}}\) are pairwise disjoint, we have \[\mathbb{P}(A_y) \geqslant\sum_{\mathcal{X},\mathcal{C}} \mathbb{P}(A_{y,\mathcal{X},\mathcal{C}}) \geqslant(\tfrac{1}{4}\Delta)^{2\ell(y)+2} \cdot (\tfrac{1}{\Delta})^{2\ell(y)+2} \cdot \frac{1}{2^{96b^2}} \leqslant 2^{-96b^2-8b-8},\] where in the equality we used that \(\ell(y)\leqslant 2b+1\). Hence, by linearity of the expectation, we have \[\begin{align} \mathbb{E}(T) = \sum_{y\in \mathcal{Y}'} \mathbb{E}(Z_y) \geqslant|\mathcal{Y}'| \cdot 2^{-96b^2 - 8b-8}&\geqslant 2^{-96b^2 - 8b-12}\cdot \frac{\Delta}{b\log^4 \Delta} &\text{by definition of \mathcal{Y}',}\\ &\geqslant\Delta^{2/3} + b&\text{by~\eqref{eq:largeDelta:9}.} \end{align}\] ◻

We now show that \(T\) is concentrated.

Subclaim 6. For any \(\lambda\geqslant 0\), \(\mathbb{P}(|T-\mathbb{E}(T)|>\lambda)\leqslant 2\exp\left(\frac{-\lambda^2}{144\Delta}\right)\).

Proof of subclaim. We aim to apply Azuma’s inequality. Let us fix a labeling \(w_1,\ldots,w_n\) of the vertices of \(D\) such that, for some \(q\), \(w_1,\ldots,w_q\in V(D)\setminus(\mathcal{K}\cup \mathcal{T})\), and \(w_{q+1},\ldots w_n\in \mathcal{K}\cup \mathcal{T}\). Note that \(T\) is determined by the \(n=|V(D)|\) assignments \(\phi'(w_1),\dots,\phi'(w_n)\).

Let \((c_1,\dots,c_n)\) and \((c_1',\dots,c_n')\) be two arbitrary sequences of \(n\) colors of \([\lceil \Delta/2\rceil ]\). In order to apply Azuma’s inequality, let us bound, for every \(j\in [n]\), the value of \[\begin{align} \delta_j = ~&\Big| \mathbb{E}\big(T \mid \phi'(w_1) = c_1 \cap \dots\cap \phi'(w_{j-1}) = c_{j-1} \cap \phi'(w_{j}) = c_{j}\big)\\ &- \mathbb{E}\big(T \mid \phi'(w_1) = c_1\cap \dots\cap \phi'(w_{j-1}) = c_{j-1} \cap \phi'(w_{j}) = c_{j}'\big) \Big|. \end{align}\]

For better readability, for every \(j\in [n]\), let \(W_j\) denote the event \(\phi'(w_1) = c_1 \cap \ldots \cap \phi'(w_j) = c_j\), and let \(W_j'\) denote the event \(\phi'(w_1) = c_1 \cap \ldots \cap \phi'(w_{j-1}) = c_{j-1} \cap \phi'(w_j) = c_j'\), so \[\delta_j = \Big|\mathbb{E}\big(T\mid W_{j}\big) - \mathbb{E}\big(T\mid W_j'\big)\Big|.\]

First, observe that changing the assigned color \(\phi'(w_j)\) of a single vertex \(w_j\) from \(c_j\) to \(c_j'\) can affect the value of \(T\) by at most \(2\), as by Condition [enum:good95triple954] at most one vertex of \(\mathcal{T}\) is colored with \(c_j\), and at most one is colored with \(c_j'\). Therefore, for every \(j\in [n]\), we have \(\delta_j \leqslant 2\). In particular, it follows that \[\label{eq:delta95j} \sum_{j=q+1}^n \delta_j^2 \leqslant 4\cdot |\mathcal{K}\cup \mathcal{T}| \leqslant 8\Delta.\tag{14}\]

Assume now that \(j\leqslant q\) and let us show a more precise bound in this case (that is, when \(w_1,\dots,w_j \notin \mathcal{K}\cup \mathcal{T}\)). Let \(N_j = N_{D^\star}(w_j) \cap \mathcal{T}\), and let \(F_j\) be the event that some vertex in \(N_j\) receives color \(c_j\) or \(c_j'\) through \(\phi'\). When \(F_j\) does not hold, observe that changing the color of \(w_j\) from \(c_j\) to \(c_{j}'\) does not affect the value of \(T\), so in particular \[\label{eq:equality95EE} \mathbb{E}(T\mid W_j \cap \overline{F_j}) = \mathbb{E}(T\mid W_j' \cap \overline{F_j}).\tag{15}\] Moreover, since \(j\leqslant q\), we have that \(\{w_1,\dots,w_j\}\) is disjoint from \(N_j\). This implies \[\label{eq:prob95FJ95bar} \mathbb{P}(\overline{F_j}) = \mathbb{P}(\overline{F_j} \mid W_j)= \mathbb{P}(\overline{F_j} \mid W_j'),\tag{16}\] and \[\label{eq:prob95FJ} \mathbb{P}(F_j) = \mathbb{P}(F_j \mid W_j)= \mathbb{P}(F_j \mid W_j') \leqslant|N_j| \cdot \frac{4}{\Delta},\tag{17}\] where the last inequality follows from the union bound and the fact that some vertex receives \(c_j\) or \(c_j'\) with probability \(\frac{2}{\lceil \Delta/2\rceil} \leqslant 4/\Delta\). Combining the inequalities above, we obtain that \[\begin{align} \delta_j &= \Big|\mathbb{E}\big(T\mid W_{j}\big) - \mathbb{E}\big(T\mid W_j'\big)\Big|\\ &= \Big| \mathbb{E}(T\mid W_j \cap F_j) \cdot \mathbb{P}(F_j\mid W_j) + \mathbb{E}(T\mid W_j \cap \overline{F_j}) \cdot \mathbb{P}(\overline{F_j}\mid W_j) \\ & -\mathbb{E}(T\mid W_j' \cap F_j) \cdot \mathbb{P}(F_j\mid W_j') - \mathbb{E}(T\mid W_j' \cap \overline{F_j}) \cdot \mathbb{P}(\overline{F_j} \mid W_j') \Big| \\ &= \Big| \mathbb{E}(T\mid W_j \cap F_j) \cdot \mathbb{P}(F_j\mid W_j) -\mathbb{E}(T\mid W_j' \cap F_j) \cdot \mathbb{P}(F_j\mid W_j')\Big| &\text{by~\eqref{eq:equality95EE} and~\eqref{eq:prob95FJ95bar},}\\ &\leqslant\Big| \mathbb{E}(T\mid W_j \cap F_j) -\mathbb{E}(T\mid W_j' \cap F_j) \Big|\cdot \frac{4\cdot |N_j|}{\Delta} &\text{by~\eqref{eq:prob95FJ}.} \end{align}\] Since changing the color of a single vertex affects \(T\) by at most \(2\), it follows that, for every \(j\leqslant q\), \[\label{eq:delta95j952} \delta_j \leqslant\frac{8|N_j|}{\Delta}.\tag{18}\] We thus have \[\begin{align} \sum_{j=1}^n \delta_j^2 &= \sum_{j=1}^q \delta_j^2 + \sum_{j=q+1}^n \delta_j^2\\ &\leqslant 2\sum_{j=1}^q \delta_j + 8\Delta &\text{by~\eqref{eq:delta95j} and the fact that \delta_j\leqslant 2,}\\ &\leqslant 8\Delta + \frac{16}{\Delta}\sum_{j=1}^q |N_j| &\text{by~\eqref{eq:delta95j952}.} \end{align}\] Recall that, by definition of \(N_j\), \(\sum_{j=1}^q |N_j|\) is in particular bounded by the number of arcs of \(D^\star\) having an extremity in \(\mathcal{T}\), which is at most \(2\cdot \Delta_{\max}(D^\star) \cdot |\mathcal{T}|\). By Claim 18 and the facts that \(\Delta+31b\leqslant 2\Delta\) and that \(|\mathcal{T}|\leqslant\Delta\), it then follows that \[\sum_{j=1}^n \delta_j^2 \leqslant 8\Delta + \frac{16}{\Delta} \cdot 2 \cdot \Delta_{\max}(D^\star) \cdot |\mathcal{T}| \leqslant 72\Delta.\] By Lemma 6, it follows that, for every \(\lambda \geqslant 0\), \[\mathbb{P}(|T-\mathbb{E}(T)| > \lambda) \leqslant 2\exp( - \lambda^2 / 144\Delta),\] as desired. The subclaim follows. ◻

We are now ready to combine the different subclaims and to conclude the proof of Claim 21. We have \[\begin{align} \mathbb{P}(\text{\phi is not i-extendable}) &\leqslant\mathbb{P}(T < b) &\text{by Subclaim~\ref{subclaim:lb95rescuers},}\\ &\leqslant\mathbb{P}\big(|T-\mathbb{E}(T)| > \Delta^{2/3}\big) &\text{by Subclaim~\ref{subclaim:events95B951},}\\ &\leqslant 2\exp\left(-\Delta^{1/3}/144\right) &\text{by Subclaim~\ref{subclaim:events95B952},}\\ &\leqslant\exp(-\log^{2}(\Delta)) &\text{by~\eqref{eq:largeDelta:8},} \end{align}\] as desired. The claim follows. ◻

4.5.3 Probabilistic analysis: conluding with Lovász Local Lemma↩︎

For every \(s\in S\), let \(A_s\) be the event that \(\phi\) is not \(s\)-extendable, and for every \(i\in [t]\) let \(A_i\) be the event that \(\phi\) is not \(i\)-extendable. By Claims 20 and 21, each of these bad events holds with probability at most \[p = \exp(-\log^2(\Delta)).\]

Note that, for every vertex \(u\in V(D)\), whether \(u\in \mathop{\mathrm{Dom}}(\phi)\) depends only on the colors assigned by \(\phi'\) to the vertex corresponding to \(u\) in and its neighbors in \(D^\star\).

Therefore, for any vertex \(s\in S\), whether \(\phi\) is \(s\)-extendable may depend only on the colors \(\phi'(u)\) given to each vertex \(u\) at distance at most \(2\) from \(s\) in the underlying graph of \(D^\star\). Recall that, by Claim 15, whenever two vertices are identified, they have at least one neighbor in common. Therefore, whether \(\phi\) is \(s\)-extendable may depend only on the colors given to vertices in \(D^\star\) corresponding to vertices in \(D\) which are at distance at most \(6\) from \(s\).

Similarly, for every \(i\in [t]\), whether \(\phi\) is \(i\)-extendable may depend only on the colors given to vertices in \(D^\star\) corresponding to vertices in \(D\) which are at distance at most \(6\) from some vertex in \(X_i\).

It follows that, for every vertex \(s\in S\), \(A_s\) is mutually independent from all events \(A_{s'}\) with \(s\) and \(s'\) being at distance at least \(13\) from each other, and from all events \(A_{i}\) with \(s\) being at distance at least \(13\) from all vertices in \(X_i\). Hence, since the underlying graph of \(D\) has maximum degree at most \(2(\Delta+b+1)\) by Claim 7, \(A_s\) is mutually independent from all other events except at most \(12\cdot (2\Delta+2b+2)^{12}\) of them.

Similarly, for every \(i\in [t]\), \(A_i\) is mutually independent from all events \(A_{s}\) with \(s\) being at distance at least \(13\) from \(X_i\), and from all events \(A_j\) with \(X_i\) being at distance at least \(13\) from \(X_j\). Since \(|X_i| \leqslant\Delta+5d \leqslant 2\Delta\) by Claim 8 [claim:dense95decomposition:i] and by 3 , \(A_i\) is mutually independent from all events but at most \((2\Delta)\cdot 12\cdot (2\Delta+2b+2)^{12}\) of them.

Since \[4 \cdot \exp(-\log^2(\Delta)) \cdot (2\Delta+2b+2)^{13} \leqslant 1\] by 9 , it follows from Lovász Local Lemma (Lemma 4) that \(\phi\) is extendable with positive probability. By Claim 17, we get that \(\vec{\chi}(D) \leqslant\Delta-b+1\), a contradiction. Theorem 2 follows. ◻

References↩︎

[1]

R. L. Brooks, “On colouring the nodes of a network,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, no. 2, pp. 194–197, 1941, doi: 10.1017/S030500410002168X.

[2]

O. V. Borodin and A. V. Kostochka, “On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density,” Journal of Combinatorial Theory, Series B, vol. 23, no. 2–3, pp. 247–250, 1977.

[3]

B. Reed, “A strengthening of Brooks’ theorem,” Journal of Combinatorial Theory, Series B, vol. 76, no. 2, pp. 136–149, 1999.

[4]

B. Reed, “\(\omega\), \(\Delta\), and \(\chi\),” Journal of Graph Theory, vol. 27, no. 4, pp. 177–212, 1998.

[5]

E. Hurley, R. de Joannis de Verclos, and R. J. Kang, “An improved procedure for colouring graphs of bounded local density,” Advances in Combinatorics, 2022, doi: 10.19086/aic.2022.7.

[6]

M. Bonamy, T. Perrett, and L. Postle, “Colouring graphs with sparse neighbourhoods: Bounds and applications,” Journal of Combinatorial Theory, Series B, vol. 155, pp. 278–317, 2022.

[7]

M. Delcourt and L. Postle, The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17)“On the list coloring version of Reed’s conjecture,” Electronic Notes in Discrete Mathematics, vol. 61, pp. 343–349, 2017, doi: https://doi.org/10.1016/j.endm.2017.06.058.

[8]

H. Jacob and H. Meyniel, “Extension of Turán’s and Brooks’ theorems and new notions of stability and coloring in digraphs,” Combinatorial Mathematics, vol. 75, pp. 365–370, 1983.

[9]

B. Mohar, “Eigenvalues and colorings of digraphs,” Linear Algebra and its Applications, vol. 432, no. 9, pp. 2273–2277, 2010.

[10]

P. Aboulker and G. Aubian, “Four proofs of the Directed Brooks’ Theorem,” Discrete Mathematics, p. 113193, 2022, doi: https://doi.org/10.1016/j.disc.2022.113193.

[11]

J. Bang-Jensen, T. Schweser, and M. Stiebitz, “Digraphs and variable degeneracy,” SIAM Journal on Discrete Mathematics, vol. 36, no. 1, pp. 578–595, 2022.

[12]

D. Gonçalves, L. Picasarri-Arrieta, and A. Reinald, “Brooks-type colourings of digraphs in linear time,” Preprint arXiv:2405.05222, 2024.

[13]

P. Aboulker, G. Aubian, and P. Charbit, “Digraph colouring and arc-connectivity,” Preprint arXiv:2304.04690, 2023.

[14]

L. Picasarri-Arrieta and M. Stiebitz, “Generalized DP-colorings of digraphs,” Preprint arXiv:2509.17471, 2025.

[15]

A. Harutyunyan, K. Kawarabayashi, L. Picasarri-Arrieta, and G. Puig i Surroca, “\((\Delta-1)\)-dicolouring of digraphs,” Preprint arXiv:2507.10266, 2025.

[16]

K. Kawarabayashi and L. Picasarri-Arrieta, “An analogue of Reed’s conjecture for digraphs,” in Proceedings of the 2025 annual ACM-SIAM symposium on discrete algorithms (SODA), 2025, pp. 3310–3324.

[17]

A. Harutyunyan and B. Mohar, “Strengthened Brooks' theorem for digraphs of girth at least three,” The Electronic Journal of Combinatorics, vol. 18, no. P195, 2011, doi: 10.37236/682.

[18]

A. D. King and B. A. Reed, “A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\),” Journal of Graph Theory, vol. 81, no. 1, pp. 30–34, 2015, doi: 10.1002/jgt.21858.

[19]

L. Picasarri-Arrieta, “Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring,” Journal of Graph Theory, vol. 106, no. 1, pp. 5–22, 2024.

[20]

K. Kawarabayashi and L. Picasarri-Arrieta, “An analogue of Reed’s conjecture for digraphs,” Preprint arXiv:2407.05827, 2024.

[21]

N. Golowich, “The m-degenerate chromatic number of a digraph,” Discrete Mathematics, vol. 339, no. 6, pp. 1734–1743, 2016.

[22]

R. Steiner, “A note on coloring digraphs of large girth,” Discrete Applied Mathematics, vol. 287, pp. 62–64, 2020.

[23]

P. Erdős, “Problems and results in number theory and graph theory,” in Proceedings of the ninth manitoba conference on numerical mathematics and computing, 1979, pp. 3–21.

[24]

A. Johansson, “Asymptotic choice number for triangle free graphs,” DIMACS Technical Report 91-95, 1996.

[25]

J. Bang-Jensen and G. Z. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd ed. London: Springer-Verlag, 2009.

[26]

M. Molloy and B. Reed, “The size of the giant component of a random graph with a given degree sequence,” Combinatorics, probability and computing, vol. 7, no. 3, pp. 295–305, 1998.

[27]

M. Molloy and B. Reed, “A bound on the total chromatic number,” Combinatorica, vol. 18, no. 2, pp. 241–280, 1998.

[28]

B. Farzad, M. Molloy, and B. Reed, “(\(\Delta-k\))-critical graphs,” Journal of Combinatorial Theory, Series B, vol. 93, no. 2, pp. 173–185, 2005, doi: https://doi.org/10.1016/j.jctb.2004.09.006.

[29]

M. Molloy and B. Reed, “Colouring graphs when the number of colours is almost the maximum degree,” Journal of Combinatorial Theory, Series B, vol. 109, pp. 134–195, 2014.

[30]

N. Alon and J. H. Spencer, The probabilistic method. John Wiley & Sons, 2016.

[31]

M. Molloy and B. Reed, Graph colouring and the probabilistic method. Berlin, Germany: Springer, 2001.

[32]

P. Erdős and L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions,” Infinite and Finite Sets, vol. 10, no. 2, pp. 609–627, 1975.

[33]

M. Talagrand, “Concentration of measure and isoperimetric inequalities in product spaces,” Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, vol. 81, pp. 73–205, 1995.

[34]

K. Azuma, “Weighted sums of certain dependent random variables,” Tohoku Mathematical Journal, Second Series, vol. 19, no. 3, pp. 357–367, 1967.

Coloring digraphs with \(\tilde{\Delta}-b\) colors