# An analogue of Reed's conjecture for digraphs

Ken-Ichi Kawarabayashi, Lucas Picasarri-Arrieta

► To cite this version:

Ken-Ichi Kawarabayashi, Lucas Picasarri-Arrieta. An analogue of Reed's conjecture for digraphs. ACM-SIAM Symposium on Discrete Algorithms (SODA25), Jan 2025, New Orleans, United States. pp.3310-3324, 10.1137/1.9781611978322.106 . hal-04639956v2

HAL Id: hal-04639956

https://inria.hal.science/hal-04639956v2

Submitted on 13 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# An analogue of Reed's conjecture for digraphs

Ken-ichi Kawarabayashi*

Lucas Picasarri-Arrieta†

## Abstract

Reed in 1998 conjectured that every graph $G$ satisfies $\chi(G) \le \lceil \frac{\Delta(G)+1+\omega(G)}{2} \rceil$. As a partial result, he proved the existence of $\varepsilon > 0$ for which every graph $G$ satisfies $\chi(G) \le \lceil (1-\varepsilon)(\Delta(G)+1) + \varepsilon\omega(G) \rceil$. We propose an analogue conjecture for digraphs. Given a digraph $D$, we denote by $\tilde{\chi}(D)$ the dichromatic number of $D$, which is the minimum number of colours needed to partition $D$ into acyclic induced subdigraphs. We let $\tilde{\omega}(D)$ denote the size of a largest biclique (a set of vertices inducing a complete digraph) of $D$ and $\tilde{\Delta}(D) = \max_{v \in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We conjecture that every digraph $D$ satisfies $\tilde{\chi}(D) \le \lceil \frac{\Delta(D)+1+\tilde{\omega}(D)}{2} \rceil$, which if true implies Reed's conjecture. As a partial result, we prove the existence of $\varepsilon > 0$ for which every digraph $D$ satisfies $\tilde{\chi}(D) \le \lceil (1-\varepsilon)(\tilde{\Delta}(D)+1) + \varepsilon\tilde{\omega}(D) \rceil$. This implies both Reed's result and an independent result of Harutyunyan and Mohar for oriented graphs.

To obtain this upper bound on $\tilde{\chi}$, we prove that every digraph $D$ with $\tilde{\omega}(D) > \frac{2}{3}(\Delta_{\max}(D)+1)$ admits an acyclic set of vertices intersecting each biclique of $D$, where $\Delta_{\max}(D) = \max_{v \in V(D)} \max(d^+(v), d^-(v))$, which generalises a result of King.

## 1 Introduction

In 1998, Reed [31] posed the following celebrated conjecture, which draws a connection between the maximum degree $\Delta(G)$, the clique number $\omega(G)$, and the chromatic number $\chi(G)$ of a graph $G$.

**CONJECTURE 1.1.** (REED [31]) Every graph $G$ satisfies $\chi(G) \le \lceil \frac{\Delta(G)+1+\omega(G)}{2} \rceil$.

As a partial result towards this conjecture, Reed proved the following.

**THEOREM 1.1.** (REED [31]) There exists $\varepsilon > 0$ such that every graph $G$ satisfies

$$ \chi(G) \le \lceil (1 - \varepsilon)(\Delta(G) + 1) + \varepsilon\omega(G) \rceil. $$

Observe that Conjecture 1.1 is exactly Theorem 1.1 for $\varepsilon = \frac{1}{2}$. Restricted to graphs with sufficiently large maximum degree, Hurley et al. [21] proved that Theorem 1.1 holds for $\varepsilon = 0.119$, improving on earlier results obtained respectively by Bonamy et al. [9] and by Delcourt and Postle [11].

The purpose of this work is to propose analogues of Conjecture 1.1 and Theorem 1.1 for digraphs. We thus need three digraph parameters that extend $\Delta$, $\omega$, and $\chi$ respectively. By extension, we mean that, if $D$ is a symmetric digraph, these digraph parameters on $D$ must coincide with $\Delta$, $\omega$, and $\chi$ on the underlying graph of $D$. One can easily check that this is actually the case for $\tilde{\Delta}$, $\tilde{\omega}$, and $\tilde{\chi}$, 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. The biclique number $\tilde{\omega}(D)$ of $D$ is the size of a largest biclique of $D$. The notions of dicolouring and dichromatic number were introduced in the late 1970s by Erdős and Neumann-Lara [28, 12]. A k-dicolouring of $D$ is a function $c: V(D) \to [k]$ such that $c^{-1}(i)$ induces an acyclic subdigraph on $D$ for each $i \in [k]$. The dichromatic number of $D$, denoted by $\tilde{\chi}(D)$, is the smallest $k \in \mathbb{N}$ such that $D$ admits a k-dicolouring. These two concepts were rediscovered by Mohar in the 2000s [26, 8] and received a lot of attention since then. It turned out that many classical results on graph colouring can be extended to digraphs with these notions, which shows that

<footnote>*National Institute of Informatics, The University of Tokyo, Japan. Research supported by JSPS KAKENHI JP20A402 and 22H05001 and by JST ASPIRE JPMJAP2302.</footnote>

<footnote>†Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France. Research supported by DIGRAPHS ANR-19-CE48-0013 and ANR-17-EURE-0004.</footnote>
dicolouring is somehow the right extension of proper colouring to digraphs. For instance, people generalised the Strong Perfect Graph Theorem [6], Gyárfás-Sumner's Conjecture [4, 3, 10], or Brooks-type results [18, 1, 2, 16]. Harutyunyan and Mohar [19] posed the following analogue of Conjecture 1.1 for oriented graphs, that are digraphs with biclique number at most 1.

**CONJECTURE 1.2.** (HARUTYUNYAN AND MOHAR [19]) Let $D$ be an oriented graph, then $\vec{\chi}(D) \leq \lfloor \frac{\tilde{\Delta}(D)}{2} \rfloor + 1$.

As a partial result towards their conjecture, they proved the following for $\varepsilon = e^{-13}$. It was later strengthened by Golowich [15], who proved it for $\varepsilon = 0.183$.

**THEOREM 1.2.** (HARUTYUNYAN AND MOHAR [19]) There exists $\varepsilon > 0$ such that every oriented graph $D$ with $\tilde{\Delta}(D)$ large enough satisfies $\vec{\chi}(D) \leq (1 - \varepsilon)\tilde{\Delta}(D)$.

We actually believe that the analogue of Conjecture 1.1 holds not only for oriented graphs but for all digraphs. We thus propose the following conjecture, which if true implies both Conjectures 1.1 and 1.2.

**CONJECTURE 1.3.** Every digraph $D$ satisfies $\vec{\chi}(D) \leq \lfloor \frac{\tilde{\Delta}(D)+1+\vec{\omega}(D)}{2} \rfloor$.

The main result of this work is the following, which implies both Theorem 1.1 (when restricted to symmetric digraphs) and Theorem 1.2 (when restricted to oriented graphs), and provide some support to Conjecture 1.3.

**THEOREM 1.3.** There exists $\varepsilon > 0$ such that every digraph $D$ satisfies $\vec{\chi}(D) \leq (1 - \varepsilon)(\tilde{\Delta}(D) + 1) + \varepsilon\vec{\omega}(D)$.

We made no attempt to maximize the value of $\varepsilon$ in our proof. In particular, applying Theorem 1.3 to obtain Theorems 1.1 and 1.2 yields values of $\varepsilon$ that are much smaller than the known ones.

Our proof of Theorem 1.3 is inspired by a short proof of Theorem 1.1 due to King and Reed [24]. Along the way, we generalise to digraphs a collection of intermediate results that we find of independent interest. We refer the reader to the recent book of Stiebitz, Schweser, and Toft [32, Chapter 6] for a complete proof of Theorem 1.1 which includes proofs of all intermediate results (on undirected graphs) mentioned later on.

The paper is organised as follows. In Section 2, we give notation on digraphs and preliminary results used in the paper. In Section 3, using the probabilistic method, we prove the following upper bound on the dichromatic number of sparse digraphs, which generalises to digraphs a classical result of Molloy and Reed [27]. Given a digraph $D$ with maximum degree $\Delta_{\max}(D) = \Delta$ and a vertex $v$ of $D$, we denote by $m^{+}(v)$ and $m^{-}(v)$ the number of arcs of $D[N^{+}(v)]$ and $D[N^{-}(v)]$ respectively. We say that $D$ is $B$-sparse if, for every vertex $v \in V(D)$, we have $\min(m^{+}(v), m^{-}(v)) \leq \Delta(\Delta - 1) - B$.

**THEOREM 1.4.** There exists an integer $\Delta_0 \geq 1$ such that the following holds. For every digraph $D$ with maximum degree $\Delta_{\max}(D) = \Delta > \Delta_0$, if $D$ is $B$-sparse with $B > \Delta \log^3 \Delta$, then $\vec{\chi}(D) \leq (\Delta + 1) - \frac{B}{4e^7\Delta}$.

In Section 4, we give a sufficient condition for a digraph to admit an acyclic set of vertices intersecting each of its bicliques, by proving the following generalisation of a result of King [23].

**THEOREM 1.5.** Let $D$ be a digraph with $\vec{\omega}(D) > \frac{2}{3}(\Delta_{\max}(D) + 1)$. Then $D$ has an acyclic set of vertices $I$ such that $\vec{\omega}(D - I) = \vec{\omega}(D) - 1$.

This result implies that, in a minimum counterexample of Theorem 1.3, there must be a significant gap between the biclique number and the maximum degree. In Section 5, we deal with vertices having a dense neighbourhood in such counterexamples. We extend a result of King and Reed [24] by proving the following.

**THEOREM 1.6.** Let $a$ and $\varepsilon$ be constants satisfying $0 < \varepsilon \leq \frac{1}{6} - 4\sqrt{a}$. There exists $\Delta(a) \geq 1$ such that the following holds. Let $D$ be a digraph with maximum degree $\Delta_{\max}(D) = \Delta \geq \Delta(a)$ satisfying $\vec{\omega}(D) \leq \frac{2}{3}(\Delta + 1)$ and let $v \in V(D)$ be such that $\max(m^{-}(v), m^{+}(v)) > (1 - a)\Delta(\Delta - 1)$. Then

$$ \vec{\chi}(D) \leq \max(\vec{\chi}(D - v), (1 - \varepsilon)(\Delta + 1)). $$

We put the pieces together and prove Theorem 1.3 in Section 6. In particular, we use a trick introduced by Harutyunyan and Mohar [19] to obtain the result with $\tilde{\Delta}$ instead of $\Delta_{\max}$. We finally propose some further research directions in Section 7. In particular, we discuss possible analogues of Conjecture 1.3 with $\tilde{\Delta}$ being replaced by smaller parameters.
## 2 Preliminaries

**2.1 General notation on digraphs** Our notation on digraphs follows [7]. A *digon* is a pair of arcs in opposite directions between the same vertices. A *simple arc* is an arc that is not in a digon. A *digraph* is *symmetric* if it contains no simple arc. An *oriented graph* is a digraph with no digon. Given an undirected graph *G*, the digraph $\overleftrightarrow{G}$ is the symmetric digraph obtained from *G* by replacing every edge with a digon. For an integer *n*, $\overrightarrow{K_n}$ is called the *complete digraph* on *n* vertices.

Let *D* be a digraph. The *underlying graph* of *D*, denoted by $UG(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 *symmetric part* of *D*, denoted by $S(D)$, is the undirected graph with vertex-set $V(D)$ in which $uv$ is an edge if and only if $\{uv, vu\}$ is a digon of *D*. Given $X, Y$ two disjoint set of vertices of *D*, we denote by $A(X, Y)$ the set of arcs $uv \in A(D)$ such that $u \in X$ and $v \in Y$.

Let *v* be a vertex of *D*. The *out-degree* (resp. *in-degree*) of *v*, denoted by $d^+(v)$ (resp. $d^-(v)$), is the number of arcs leaving (resp. entering) *v*. We define the *maximum degree* of *v* as $d_{\max}(v) = \max\{d^+(v), d^-(v)\}$, and the *minimum degree* of *v* as $d_{\min}(v) = \min\{d^+(v), d^-(v)\}$. We can then define the corresponding maximum degrees of *D*:

$$ \Delta_{\max}(D) = \max\{d_{\max}(v) \mid v \in V(D)\} \quad \text{and} \quad \Delta_{\min}(D) = \max\{d_{\min}(v) \mid v \in V(D)\}. $$

The *maximum geometric mean* of *D* is defined as $\tilde{\Delta}(D) = \max_{v \in V(D)} \sqrt{d^-(v) \cdot d^+(v)}$. By definition, observe that we have $\Delta_{\min}(D) \le \tilde{\Delta}(D) \le \Delta_{\max}(D)$. We say that *D* is *Δ-diregular* if, for every vertex $v \in V(D)$, $d^-(v) = d^+(v) = \Delta$. Note that *D* being *diregular* implies $\Delta_{\min}(D) = \Delta_{\max}(D)$ but the converse is not true.

A *list assignment* $L$ of *D* is a function that associates a list of colours to every vertex $v$ of *D*. It is a *k-list assignment* if $|L(v)| \ge k$ holds for every vertex $v$ of *D*. Let $L$ be a list assignment. An *L-dicolouring* of *D* is a dicolouring $\alpha$ of *D* such that, for every vertex $v$ of *D*, $\alpha(v) \in L(v)$. We say that *D* is *L-dicolourable* if *D* admits an *L-dicolouring*. Given an integer $k$, we say that *D* is *k-dichoosable* if, for every $k$-list assignment $L$ of *D*, *D* is *L-dicolourable*.

**2.2 Probabilistic tools** Our proof of Theorem 1.3 contains some probabilistic arguments. We briefly recall here two classical results used later. The reader unfamiliar with the probabilistic method is referred to [5] and [27]. We first need the symmetric version of the Lovász Local Lemma, due to Erdős and Lovász [13].

**LEMMA 2.1. (LOVÁSZ LOCAL LEMMA)** 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 $\text{Pr}(A_i) \le p$ for all $1 \le i \le n$. If

$$ ep(d+1) \le 1, $$

then $\text{Pr}(\bigwedge_{i=1}^n \overline{A_i}) > 0$.

The second result we need is the celebrated concentration bound due to Talagrand [33]. We use it in the following form (see [22, Theorem 6.3]).

**LEMMA 2.2. (TALAGRAND'S INEQUALITY)** Let $X$ be a non-negative random variable, not identically 0, which is determined by $n$ independent trials and satisfying the following for some $c, r > 0$:

1. Changing the outcome of any one trial can affect $X$ by at most $c$, and

2. for any $s$, if $X \ge s$ then there is a set of at most $rs$ trials whose outcomes certify that $X \ge s$.

Then

$$ \text{Pr}(|X - \mathbf{E}(X)| > t) \le 4 \exp \left( - \frac{t^2}{8rc^2(4\mathbf{E}(X) + t)} \right) $$

for any real number $t$ with $t > 96c\sqrt{r\mathbf{E}(X)} + 128rc^2$.
### 3 Colouring sparse digraphs

Our first goal is to prove Theorem 1.4, which is the directed analogue of the following result due to Molloy and Reed [27, Theorem 10.5] on the chromatic number of sparse graphs. For a vertex $v$ of a graph $G$, we denote by $m(v)$ the number of edges of $G[N(v)]$. We say that $G$ is B-sparse if $m(v) \le (\Delta(G)/2) - B$ for every $v \in V(G)$.

**THEOREM 3.1. (MOLLOY AND REED [27])** Let $\Delta$ be an integer large enough and $G$ be a graph with maximum degree $\Delta$. If $G$ is B-sparse with $B > \Delta \log^3 \Delta$, then

$$ \chi(G) \le (\Delta + 1) - \frac{B}{e^6 \Delta}. $$

We first recall Theorem 1.4 here for the reader's convenience.

**THEOREM 3.2.** There exists an integer $\Delta_0 \ge 1$ such that the following holds. For every digraph $D$ with maximum degree $\Delta_{\max}(D) = \Delta > \Delta_0$, if $D$ is B-sparse with $B > \Delta \log^3 \Delta$, then

$$ \vec{\chi}(D) \le (\Delta + 1) - \frac{B}{4e^7 \Delta}. $$

We will actually use Theorem 3.2 in the following form in Section 6.

**COROLLARY 3.1.** There exists $\Delta_1 \ge 2$ such that the following holds. Let $D$ be a digraph with maximum degree $\Delta_{\max}(D) = \Delta \ge \Delta_1$ and $a \in \mathbb{R}$ be such that $a > \frac{\log^3 \Delta}{\Delta-1}$, and for every vertex $v \in V(D)$, $\min(m^+(v), m^-(v)) \le (1-a)\Delta(\Delta-1)$. Then

$$ \vec{\chi}(D) \le \left(1 - \frac{a}{5e^7}\right) (\Delta + 1). $$

*Proof.* By assumption $D$ is $B_a$-sparse for $B_a = a\Delta(\Delta-1) > \Delta \log^3 \Delta$. Hence, by taking $\Delta_1 \ge \Delta_0$, we obtain by Theorem 3.2 that

$$ \vec{\chi}(D) \le \left(1 - \frac{a}{4e^7}\right) (\Delta + 1) + \frac{a}{2e^7} \le \left(1 - \frac{a}{5e^7}\right) (\Delta + 1), $$

where in the second inequality we used $\Delta_1 \ge 9$. $\square$

The remainder of this section is devoted to the proof of Theorem 3.2. We first briefly justify that we only have to prove it for $\Delta$-diregular digraphs.

**LEMMA 3.1.** Let $D$ be a B-sparse digraph with maximum degree $\Delta_{\max}(D) = \Delta$. There exists a B-sparse $\Delta$-diregular digraph $H$ such that $\vec{\chi}(D) \le \vec{\chi}(H)$.

*Proof.* We repeat the following process until $D$ is $\Delta$-diregular. Add to $D$ a disjoint copy of $\bar{D}$, the digraph obtained from $D$ by reversing every arc. Then for every vertex $v \in V(D)$ such that $d_D^+(v) < \Delta$, we add the arc $vv'$, where $v'$ is the copy of $v$ in $\bar{D}$. Similarly, for every vertex $v$ such that $d_D^-(v) < \Delta$, we add the arc $v'v$. Let $D'$ be the obtained digraph. Note that $\vec{\chi}(D) \le \vec{\chi}(D')$ trivially holds as $D$ is a subdigraph of $D'$. Observe also that, for every vertex $v \in V(D)$, we have $m_D^+(v) = m_{D'}^+(v) = m_{D'}^-(v')$ and $m_D^-(v) = m_{D'}^-(v) = m_{D'}^+(v')$. Hence, as $D$ is B-sparse, so is $D'$. Observe finally that, for every vertex $v \in V(D)$, $d_{D'}^+(v) = d_{D'}^-(v') = \min(d_D^+(v) + 1, \Delta)$ and $d_{D'}^-(v) = d_{D'}^+(v') = \min(d_D^-(v) + 1, \Delta)$. Hence, repeating this process at most $\Delta$ times, we eventually find the desired digraph $H$. $\square$

A partial $(k, \ell)$-dicolouring $\alpha$ of a digraph $D$ is a $k$-dicolouring of an induced subdigraph of $D$ such that, for every vertex $v$, either $\ell$ colours appear twice in $N^-(v)$ or $\ell$ colours appear twice in $N^+(v)$. We formally have

$$ |\{c \in [k] \mid \exists u, w \in N^-(v), u \ne w, \alpha(u) = \alpha(w) = c\}| \ge \ell $$

$$ \text{or} \quad |\{c \in [k] \mid \exists u, w \in N^+(v), u \ne w, \alpha(u) = \alpha(w) = c\}| \ge \ell. $$

**LEMMA 3.2.** Let $D$ be a $\Delta$-diregular digraph and $k, \ell$ be two integers such that $k \le \Delta + 1 - \ell$. If $D$ admits a partial $(k, \ell)$-dicolouring, then $\vec{\chi}(D) \le \Delta + 1 - \ell$.
*Proof.* Assume that $D$ admits a partial $(k, \ell)$-dicolouring. We let $\alpha$ be a partial $(\Delta+1-\ell, \ell)$-dicolouring of $D$ for which the number of uncoloured vertices is minimum, the existence of which is guaranteed as $k \le \Delta+1-\ell$. We claim that $\alpha$ is a dicolouring of $D$, hence implying $\chi(D) \le \Delta+1-\ell$. Assume this is not the case, so there is a vertex $v$ which is not coloured by $\alpha$. By definition of a partial $(\Delta+1-\ell, \ell)$-dicolouring, we have $|\alpha(N^-(v))| \le \Delta-\ell$ or $|\alpha(N^+(v))| \le \Delta-\ell$. Hence we can choose for $v$ a colour of $[\Delta+1-\ell]$ that is not appearing either in its in- or in its out-neighbourhood. Colouring $v$ with this specific colour extends $\alpha$ into a partial $(\Delta+1-\ell, \ell)$-dicolouring of $D$ with fewer uncoloured vertices, a contradiction to the choice of $\alpha$. □

We are now ready to prove Theorem 3.2.

*Proof.* We do not give the explicit value of $\Delta_0$, we simply assume in what follows that it is arbitrarily large. We assume that $D$ is $\Delta$-diregular, for otherwise we may prove the result for the $B$-sparse $\Delta$-diregular digraph $H$ obtained by Lemma 3.1, and conclude that $\chi(D) \le \chi(H) \le (\Delta+1) - \frac{B}{4e^\tau\Delta}$.

We use the probabilistic method. Let us fix $k = \lfloor \frac{\Delta}{2} \rfloor$. We randomly colour every vertex of $D$ with a colour of $[k]$. Then we simultaneously uncolour every vertex $v$ having at least one in-neighbour and at least one out-neighbour sharing its colour. Our goal is to show that with non-zero probability, the obtained colouring $\alpha$ is a partial $(k, \ell)$-dicolouring of $D$, where $\ell = \frac{B}{4e^\tau\Delta}$. Observe that we have $k \le \Delta+1-\ell$ as $B \le \Delta(\Delta-1)$. Hence, if $\alpha$ is indeed a partial $(k, \ell)$-dicolouring of $D$, the result follows from Lemma 3.2. Note that $\alpha$ is necessarily a dicolouring of an induced subdigraph of $D$, for otherwise $D$, partially coloured with $\alpha$, contains a monochromatic directed cycle, the vertices of which should have been uncoloured in the process. It remains to show that, for every vertex of $D$, $\ell$ colours are repeated either in its in-neighbourhood or in its out-neighbourhood.

For each vertex $v$, we let $N_v$ be $N^+(v)$ if $m^+(v) \le m^-(v)$ and $N^-(v)$ otherwise. We also let $B_v$ be the number of missing arcs in $D[N_v]$, that is $B_v = \Delta(\Delta-1) - \min(m^-(v), m^+(v))$. Note that $B_v \ge B > \Delta \log^3 \Delta$. Let $X_v$ be the random variable corresponding to the number of colours that are assigned to at least two vertices in $N_v$ and are retained by all these vertices. We also define $Y_v$ as the number of colours assigned to at least two vertices in $N_v$ that are not linked by a digon, but not necessarily retained. Finally, we define $Z_v$ as the number of colours assigned to at least two vertices in $N_v$ that are not linked by a digon and one of these vertices does not retain its colour. We thus have $X_v = Y_v - Z_v$.

We let $A_v$ be the event that $X_v < \ell$. Our goal is to show that none of the events $A_v$ occurs with non-zero probability. To do so, we will prove that, for each vertex $v$, the probability that $A_v$ occurs is small enough and then conclude by the Lovász Local Lemma (Lemma 2.1).

**CLAIM 3.1.** For every vertex $v$, we have $\mathbf{E}(X_v) \ge \frac{B_v}{2e^\tau\Delta}$

*Proof of claim.* For every pair of vertices $u, w \in N_v$ and every colour $c \in [k]$, we let $A_{u,w}^c$ be the event that $u, w$ are exactly the vertices coloured $c$ in $N_v$ and they both retain their colour. We let $X_{u,w}^c$ be the binary random variable equals to 1 if $A_{u,w}^c$ occurs and 0 otherwise. We clearly have $X_v \ge \sum_{u,w,c} X_{u,w}^c$.

Assume $u$ and $w$ are not linked by a digon. If $uw$ is a simple arc of $D$, then $A_{u,w}^c$ occurs if and only if both $u$ and $w$ are coloured $c$ and no vertex in $N = (N_v \cup N^-(u) \cup N^+(w)) - \{u, w\}$ receives colour $c$. If the arc $uw$ is missing, then $A_{u,w}^c$ occurs in particular if both $u$ and $w$ are coloured $c$ and no vertex in $N = (N_v \cup N^+(u) \cup N^-(w)) - \{u, w\}$ receives colour $c$. In both cases, as $k = \lfloor \frac{\Delta}{2} \rfloor$, we have $|N| \le 3\Delta \le 7k$, which implies

$$ \mathbf{Pr}(A_{u,w}^c) \ge \left(\frac{1}{k}\right)^2 \left(1 - \frac{1}{k}\right)^{7k}. $$

By definition of $B_v$ we have at least $\frac{B_v}{2}$ distinct pair of vertices that are not linked by a digon in $N^+(v)$. We also have $k$ choices for colour $c$. By linearity of the expectation we thus obtain

$$ \mathbf{E}(X_v) \ge k \frac{B_v}{2} \left(\frac{1}{k}\right)^2 \left(1 - \frac{1}{k}\right)^{7k} \ge \frac{B_v}{\Delta} \left(1 - \frac{1}{k}\right)^{7k} \ge \frac{B_v}{2e^7\Delta}, $$

where in the last inequality we used that $k = \lfloor \frac{\Delta}{2} \rfloor$ is large enough and $\lim_{k \to +\infty} \left(1 - \frac{1}{k}\right)^{7k} = \frac{1}{e^7} > \frac{1}{2e^7}$. ◇
**CLAIM 3.2.** For every vertex $v$, we have $\mathbf{E}(X_v) \le \mathbf{E}(Y_v) \le \frac{3B_v}{\Delta}$

*Proof of claim.* Since $X_v = Y_v - Z_v$ it is clear that $\mathbf{E}(X_v) \le \mathbf{E}(Y_v)$. Given two vertices $u, w \in N_v$ that are not linked by a digon and a colour $c \in [k]$, we let $Y_{u,w}^c$ be the binary random variable equals to 1 if both $u$ and $w$ are coloured $c$ and 0 otherwise. We have $Y_v \le \sum_{u,w,c} Y_{u,w}^c$ and $\mathbf{Pr}(Y_{u,w}^c = 1) = \frac{1}{k^2}$. Since we have at most $B_v$ choices for the pair $u, w$ and exactly $k$ for colour $c$, by linearity of the expectation we obtain

$$ \mathbf{E}(X_v) \le \mathbf{E}(Y_v) \le k B_v \left(\frac{1}{k}\right)^2 \le \frac{3B_v}{\Delta}, $$

where in the last inequality we used $k = \lfloor \frac{\Delta}{2} \rfloor \ge \frac{\Delta}{3}$.

◇

**CLAIM 3.3.** For every vertex $v$, $\mathbf{Pr}(|X_v - \mathbf{E}(X_v)| > \log \Delta \sqrt{\mathbf{E}(X_v)}) < \frac{1}{\Delta^s}$.

*Proof of claim.* Let us set $t = \frac{1}{2} \log \Delta \sqrt{\mathbf{E}(X_v)}$. Recall that $X_v = Y_v - Z_v$, so by linearity of the expectation we have $\mathbf{E}(X_v) = \mathbf{E}(Y_v) - \mathbf{E}(Z_v)$, and $|X_v - \mathbf{E}(X_v)| \le |Y_v - \mathbf{E}(Y_v)| + |Z_v - \mathbf{E}(Z_v)|$. In particular, this implies

$$ (3.1) \qquad \mathbf{Pr}(|X_v - \mathbf{E}(X_v)| > 2t) \le \mathbf{Pr}(|Y_v - \mathbf{E}(Y_v)| > t) + \mathbf{Pr}(|Z_v - \mathbf{E}(Z_v)| > t). $$

We will use Talagrand's inequality (Lemma 2.2) to bound both $\mathbf{Pr}(|Y_v - \mathbf{E}(Y_v)| > t)$ and $\mathbf{Pr}(|Z_v - \mathbf{E}(Z_v)| > t)$. Observe that changing the colour of exactly one vertex affects $Y_v$ by at most 1. Also if $Y_v \ge s$ then there exists a set of 2s vertices whose colours certify $Y_v \ge s$: for each of the s colours we may choose two vertices not linked by a digon sharing this colour. Combining Claims 3.1 and 3.2 we obtain $\mathbf{E}(Y_v) \le 6e^7 \mathbf{E}(X_v)$. Hence, $\Delta$ being is sufficiently large, we have $t > 96\sqrt{2\mathbf{E}(Y_v)} + 256$, which allows us to apply Talagrand's inequality to $Y_v$ and obtain

$$ (3.2) \qquad \mathbf{Pr}(|Y_v - \mathbf{E}(Y_v)| > t) \le 4 \exp \left( - \frac{t^2}{64\mathbf{E}(Y_v) + 16t} \right). $$

We now consider $Z_v$. Changing the colour of exactly one vertex affects $Z_v$ by at most 2. Also if $Z_v \ge s$ then there exists a set of 4s vertices whose colours certify $Z_v \ge s$: for each of the s colours we may choose four vertices $a, b, b^-, b^+$ sharing this colour, $a \ne b$, such that $a$ and $b$ are not linked by a digon in $D$, and $b^-b, bb^+ \in A(D)$ ($a, b^-, b^+$ are not necessarily distinct). Observe that $Z_v \le Y_v$, so in particular $\mathbf{E}(Z_v) \le \mathbf{E}(Y_v) \le 6e^7 \mathbf{E}(X_v)$ by Claims 3.1 and 3.2. Hence, $\Delta$ being sufficiently large, we have $t > 192\sqrt{4\mathbf{E}(Z_v)} + 2048$, which allows us to apply Talagrand's inequality to $Z_v$ and obtain

$$ (3.3) \qquad \mathbf{Pr}(|Z_v - \mathbf{E}(Z_v)| > t) \le 4 \exp \left( - \frac{t^2}{512\mathbf{E}(Z_v) + 128t} \right). $$

Combining (3.1), (3.2), and (3.3) together with $\mathbf{E}(Z_v) \le \mathbf{E}(Y_v) \le 6e^7 \mathbf{E}(X_v)$ we obtain

$$ \begin{aligned} \mathbf{Pr}(|X_v - \mathbf{E}(X_v)| > 2t) &\le 8 \exp \left( - \frac{t^2}{3072e^7 \mathbf{E}(X_v) + 128t} \right) = 8 \exp \left( - \frac{\log^2 \Delta}{12288e^7 + 256 \frac{\log \Delta}{\sqrt{\mathbf{E}(X_v)}}} \right) \\ &\le 8 \exp \left( - \frac{\log^2 \Delta}{12288e^7 + 256 \sqrt{2e^7} \frac{1}{\sqrt{\log \Delta}}} \right), \end{aligned} $$

where in the last inequality we used $\mathbf{E}(X) \ge \frac{B_v}{2e^7 \Delta}$ and $B_v \ge \Delta \log^3 \Delta$. As $\Delta$ is sufficiently large, we obtain

$$ \mathbf{Pr}(|X_v - \mathbf{E}(X_v)| > \log \Delta \sqrt{\mathbf{E}(X_v)}) < \frac{1}{\Delta^5}, $$

which concludes the proof of the claim.

◇
By Claim 3.1 together with the fact that $B_v \ge B \ge \Delta \log^3 \Delta$, we have

$$ \mathbf{E}(X_v) - \log \Delta \sqrt{\mathbf{E}(X_v)} \ge \frac{B_v}{2e^7 \Delta} \left( 1 - \log \Delta \sqrt{\frac{2e^7 \Delta}{B_v}} \right) \ge \frac{B}{2e^7 \Delta} \left( 1 - \sqrt{\frac{2e^7}{\log \Delta}} \right). $$

By choice of $\ell$, we thus have $\mathbf{E}(X_v) - \log \Delta \sqrt{\mathbf{E}(X_v)} \ge 2\ell \left(1 - \sqrt{\frac{2e^7}{\log \Delta}}\right)$, which is larger than $\ell$ for $\Delta$ large enough. Hence we obtain

$$ \mathbf{Pr}(A_v) = \mathbf{Pr}(X_v < \ell) \le \mathbf{Pr} \left( X_v < \mathbf{E}(X) - \log \Delta \sqrt{\mathbf{E}(X)} \right) \le \mathbf{Pr} \left( |X_v - \mathbf{E}(X)| > \log \Delta \sqrt{\mathbf{E}(X)} \right). $$

Therefore, by Claim 3.3, we have $\mathbf{Pr}(A_v) < \frac{1}{\Delta^5}$. Observe finally that the value of $X_v$ depends only on the colour of vertices at distance at most 2 of $v$ in $UG(D)$. Hence, each event $A_v$ is mutually independent of all other events $A_u$ except at most $(2\Delta)^4 = d$ of them. For every vertex $v$, we have $e\mathbf{Pr}(A_v)(d+1) \le e^{\frac{16\Delta^4+1}{\Delta^5}}$, which is smaller than 1 if $\Delta$ is large enough. Hence by the Lovász Local Lemma (Lemma 2.1) none of the events $A_v$ occurs with non-zero probability, which concludes the proof. $\square$

## 4 Hitting every maximum biclique with an acyclic set of vertices

Let $G$ be a graph with maximum degree $\Delta(G) \le 3k-1$. Haxell [20] proved that, if the vertices of $G$ can be partitionned into $r$ cliques $C_1, \dots, C_r$ of size $\ge 2k$, then $G$ contains an independent set $S$ of size $r$. In particular, $S$ intersects each clique $C_i$. Using this result, Rabern [30] proved that every graph $G$ satisfying $\omega(G) \ge \frac{3}{4}(\Delta(G)+1)$ contains an independent set intersecting every maximum clique of $G$. This was later improved to $\omega(G) > \frac{2}{3}(\Delta(G)+1)$ by King [23], which is best possible.

The goal of this section is to prove Theorem 1.5, which generalises King's result. We first prove the following result, which generalises to digraphs a more precise version of Haxell's result obtained by King [23, Theorem 5].

**THEOREM 4.1.** Let $k$ be a positive integer and $D$ be a digraph with vertices partitioned into bicliques $C_1, \dots, C_r$. If for every $i \in [r]$ and every $v \in C_i$, $v$ has at most $k$ out-neighbours outside $C_i$ and at most $|C_i| - k$ in-neighbours outside $C_i$, then $D$ contains an acyclic set of size $r$.

Given a digraph $D$ whose vertices are partitionned into independent sets $V_1, \dots, V_r$, an acyclic system of representative (with respect to $V_1, \dots, V_r$), or ASR for conciseness, is an acyclic set of vertices $X$ such that, for every $i \in [r]$, $|V_i \cap X| = 1$. If we relax this condition to $|V_i \cap X| \le 1$, then $X$ is a partial ASR. Theorem 4.1 can be restated in terms of ASR as follows.

**THEOREM 4.2.** Let $k$ be a positive integer and $D$ be a digraph with vertices partitioned into independent sets $V_1, \dots, V_r$. If every vertex $v \in V_i$ satisfies $d^+(v) \le k$ and $d^-(v) \le |V_i| - k$, then $D$ admits an ASR.

*Proof.* For any subset of indices $I \subseteq [r]$ we denote by $V_I$ the set of vertices $\bigcup_{i \in I} V_i$. Given a set of vertices $X \subseteq V(D)$, we denote by $\iota(X)$ the set of indices $\{i \in [r] \mid V_i \cap X \ne \emptyset\}$. For a single vertex $v$, we denote by $\iota(v)$ the integer $i$ such that $v \in V_i$.

We proceed by induction on $r \ge 1$. The result being trivial when $r=1$, we assume $r \ge 2$. Let us fix any vertex $x_1 \in V_r$, we will show as a stronger result that there exists an ASR containing $x_1$. Assume for a contradiction that no such ASR exists.

Let $I \subseteq [r-1]$ and $X, Y \subseteq (V_I \cup \{x_1\})$. We say that $(I, X, Y)$ is a good triplet if each of the following properties holds:

(1) $X$ and $Y$ are two disjoint acyclic sets with $x_1 \in X$;

(2) $Y$ is an ASR of $D[V_I]$ (with respect to $(V_i)_{i \in I}$);

(3) every vertex in $Y$ has exactly one in-neighbour in $X$ and every vertex in $X$ has at least one out-neighbour in $Y$, in particular $|X| \le |Y|$; and

(4) every vertex $v \in V_I \cup \{x_i\}$ has an in-neighbour in $X$ or an out-neighbour in $Y$.
We first justify that there exists no good triplet in D.

CLAIM 4.1. D admits no good triplet (I, X, Y).

*Proof of claim.* Assume for a contradiction that $(I, X, Y)$ is a good triplet of $D$. The assumption on the degrees in $D$ implies in particular $d^+(x) \le k$ for every vertex $x \in X$ and $d^-(y) \le |V_{\iota(y)}| - k$ for every vertex $y \in Y$. Observe that $|X| \le |Y| = |I|$ by (3) and (2). We thus have

$$ \sum_{x \in X} d^+(x) + \sum_{y \in Y} d^-(y) \le k|I| + \sum_{i \in I} (|V_i| - k) = |V_I|. $$

On the other hand, we know by (4) that $(V_I \cup \{x_1\}) \subseteq (N^+(X) \cup N^-(Y))$. This implies

$$ \sum_{x \in X} d^+(x) + \sum_{y \in Y} d^-(y) \ge |N^+(X) \cup N^-(Y)| \ge |V_I| + 1, $$

yielding the contradiction.

◊

Our goal is now to show that $D$ admits an infinite sequence $(Y_i)_{i \ge 1}$ of partial ASR, such that each $Y_i$ is a proper subset of $Y_{i+1}$. This will yield the contradiction since such a sequence has length at most $r$.

Let $R_1$ be an ASR of $D[V_{[r-1]}]$ (with respect to $V_1, \dots, V_{r-1}$) for which the size of $Y_1 = Y'_1 = N^+(x_1) \cap R_1$ is minimum. The existence of $R_1$ is guaranteed by induction on $r$. Observe that $Y_1 \ne \emptyset$ for otherwise $R_1 \cup \{x_1\}$ is an ASR of $D$ containing $x_1$. We let $X_1$ be the singleton $\{x_1\}$. We will recursively build $(R_{i+1}, X_{i+1}, Y_{i+1}, Y'_{i+1})$ from $(R_i, X_i, Y_i, Y'_i)$ in such a way that, for every $i \ge 1$, each of the following properties holds.

(a) $X_i = \{x_1, \dots, x_i\}$ is acyclic. If $i > 1$ then $x_i \in V_{\iota(Y_{i-1})}$.

(b) $R_i$ is an ASR of $D[V_{[r-1]}]$ such that for every $1 \le j \le i - 1$, $R_i \cap N^+(x_j) = Y'_j$. Subject to this property, $Y'_i = N^+(x_i) \cap R_i$ has minimum size.

(c) $Y_i = \bigsqcup_{1 \le j \le i} Y'_j$ and $Y'_i \ne \emptyset$.

Observe that $(R_1, X_1, Y_1, Y'_1)$ satisfies (a), (b), and (c). Also, the existence of such an infinite sequence $(R_i, X_i, Y_i, Y'_i)_{i \ge 1}$ implies the desired infinite sequence $(Y_i)_{i \ge 1}$ of partial ASR, yielding the contradiction.

Hence we assume that for some $i \ge 1$, there exists $(R_i, X_i, Y_i, Y'_i)_{1 \le j \le i}$ such that, for each $j \in [i]$, (a), (b), and (c) hold. We construct $(R_{i+1}, X_{i+1}, Y_{i+1}, Y'_{i+1})$ as follows.

* We let $x_{i+1}$ be a vertex in $V_{\iota(Y_i)} - (X_i \cup Y_i)$ such that

$$ (4.4) \qquad N^-(x_{i+1}) \cap X_i = \emptyset \quad \text{and} \quad N^+(x_{i+1}) \cap Y_i = \emptyset. $$

If such a vertex $x_{i+1}$ exists then $X_{i+1} = \{x_1, \dots, x_{i+1}\}$ is acyclic as $x_{i+1}$ is a source in $D[X_{i+1}]$ and $X_i = \{x_1, \dots, x_i\}$ is acyclic by recurrence, so (a) holds.

Let us justify the existence of $x_{i+1}$. If no such vertex exists, then $X_i$ and $Y_i$ are two disjoint acyclic sets such that $x_1 \in X_i$, with $Y_i$ being an ASR of $V_{\iota(Y_i)}$. Combining conditions (b) and (c) we obtain that $(N^+(x_1), \dots, N^+(x_i))$ partitions $Y_i$ into non-empty parts, so in particular every vertex in $Y_i$ has exactly one in-neighbour in $X_i$ and every vertex in $X_i$ has at least one out-neighbour in $Y_i$. Hence, if no vertex in $V_{\iota(Y_i)} - (X_i \cup Y_i)$ satisfies (4.4), we deduce that $(\iota(Y_i), X_i, Y_i)$ is a good triplet, a contradiction to Claim 4.1.

* We let $R_{i+1}$ be an ASR of $D[V_{[r-1]}]$ such that for every $1 \le j \le i$, $R_{i+1} \cap N^+(x_j) = Y'_j$, and subject to this property, $Y'_{i+1} = N^+(x_{i+1}) \cap R_{i+1}$ has minimum size. The existence of $R_{i+1}$ is guaranteed as $R_i$ is such an ASR. Hence (b) is maintained.

* It remains to show that (c) is maintained, that is $Y'_{i+1} \ne \emptyset$ and $Y'_{i+1} \cap Y_i = \emptyset$. First we have $Y'_{i+1} \cap Y_i = \emptyset$ by (4.4). Now assume for a contradiction that $Y'_{i+1} = \emptyset$, which together with (4.4) implies that $x_{i+1}$ has no out-neighbour in $R_{i+1}$.
By recurrence we know that $(Y'_1, \dots, Y'_i)$ partitions $Y_i$. As $x_{i+1}$ belongs to $V_{\iota(Y_i)} - (X_i \cup Y_i)$ there exists a unique $j \le i$ such that $\iota(x_{i+1}) \in \iota(Y'_j)$. As $Y'_j$ is a partial ASR, there exists a unique $y_j \in Y'_j \cap V_{\iota(x_{i+1})}$. Consider the set $\tilde{R}_j$ defined as

$$ \tilde{R}_j = R_{i+1} - \{y_j\} \cup \{x_{i+1}\}. $$

Observe that $\tilde{R}_j$ is necessarily acyclic as $x_{i+1}$ has no out-neighbour in $R_{i+1}$ and $R_{i+1}$ is an ASR of $D[V_{[r-1]}]$. Also, since $y_j \in V_{\iota(x_{i+1})}$, we obtain that $\tilde{R}_j$ is an ASR of $D[V_{[r-1]}]$.

Since $x_{i+1}$ has no in-neighbour in $X_i$ by (4.4), for every $1 \le \ell < j$, we have $\tilde{R}_j \cap N^+(x_\ell) = R_{i+1} \cap N^+(x_\ell) = Y'_\ell$. We finally have $\tilde{R}_j \cap N^+(x_j) = (R_{i+1} \cap N^+(x_j)) - \{y_j\} = Y'_j - \{y_j\}$, a contradiction to the choice of $R_j$.

Hence (a), (b), and (c) are maintained, and the result follows. □

With Theorem 4.1 in hand, we are now going to prove Theorem 1.5. We need one additional intermediate result due to Hajnal. Let $G$ be a (di)graph. We denote by $\mathcal{C}(G)$ the set of all maximum (bi)cliques of $G$. Given a collection $\mathcal{C} \subseteq \mathcal{C}(G)$ of maximum (bi)cliques of $G$, we denote by $\mathrm{IG}(\mathcal{C})$ the intersection graph of $\mathcal{C}$, i.e. the undirected graph with vertex-set $\mathcal{C}$ which contains an edge between $C_1$ and $C_2$ whenever $C_1 \cap C_2 \ne \emptyset$.

**LEMMA 4.1. (HAJNAL [17])** Let $G$ be a graph and $\mathcal{C}$ be a collection of maximum cliques of $G$, then

$$ |\bigcap \mathcal{C}| + |\bigcup \mathcal{C}| \ge 2\omega(G). $$

We are now ready to prove Theorem 1.5, that we first restate here for the reader's convenience.

**THEOREM 4.3.** Let $D$ be a digraph with $\vec{\omega}(D) > \frac{2}{3}(\Delta_{\max}(D) + 1)$. Then $D$ has an acyclic set of vertices $I$ such that $\vec{\omega}(D - I) = \vec{\omega}(D) - 1$.

*Proof.* Let $\mathcal{H}$ be $\mathrm{IG}(\mathcal{C}(D))$. We denote by $\mathcal{H}_1, \dots, \mathcal{H}_r$ the connected components of $\mathcal{H}$. For each $i \in [r]$, let $X_i = \bigcap_{C \in V(\mathcal{H}_i)}$ and $Y_i = \bigcup_{C \in V(\mathcal{H}_i)}$.

We first show that, for every $i \in [r]$, $X_i \ne \emptyset$. If this is not the case, then there exist $C_1, C_2, C_3 \in \mathcal{C}(D)$ such that $C_2$ intersects both $C_1$ and $C_3$, and $C_1 \cap C_3 = \emptyset$. Since $C_1$ and $C_3$ are disjoint, we can assume without loss of generality that $|C_1 \cap C_2| \le \frac{1}{2}\vec{\omega}(D)$. Therefore $|C_1 \cup C_2| \ge \frac{3}{2}\vec{\omega}(D) > \Delta + 1$, which implies that vertices in $C_1 \cap C_2$ have out-degree larger than $\Delta$, a contradiction.

Hence $X_i = \bigcap_{C \in V(\mathcal{H}_i)} C \ne \emptyset$ holds for every $i \in [r]$. Let $D'$ be the subdigraph of $D$ induced by $\bigcup_{i \in [r]} X_i$. Let us show that we can apply Theorem 4.1 to $D'$, the vertices of $D'$ being partitioned into bicliques $X_1, \dots, X_r$, with $k = \lfloor \frac{1}{3}(\Delta + 1) \rfloor$. Let $i$ be any index of $[r]$ and $v_i$ be any vertex in $X_i$. Observe that $v_i$ has at least $\vec{\omega}(D) - 1$ out-neighbours in $Y_i = \bigcup_{C \in V(\mathcal{H}_i)} C$, so the out-degree of $v_i$ outside $X_i$ in $D'$ is at most $\Delta - \vec{\omega}(D) + 1 \le \frac{1}{3}(\Delta + 1)$. Since it is an integer, the out-degree of $v_i$ outside $X_i$ in $D'$ is thus at most $k$. On the other hand, $v_i$ has at most $\Delta - |Y_i| + 1$ in-neighbours outside $X_i$ in $D'$. By Lemma 4.1 applied to $S(D)$ we have $|Y_i| \ge 2\vec{\omega}(D) - |X_i| > \frac{4}{3}(\Delta + 1) - |X_i|$. Hence $v_i$ has at most $|X_i| - \frac{1}{3}(\Delta + 1) \le |X_i| - k$ in-neighbours outside $X_i$ in $D'$.

Therefore, we can apply Theorem 4.1 to $D'$, and conclude that $D'$ admits an acyclic set $I$ such that $\vec{\omega}(D' - I) = \vec{\omega}(D) - 1$. By construction of $D'$, $I$ is also an acyclic set of $D$ such that $\vec{\omega}(D - I) = \vec{\omega}(D) - 1$, a contradiction. □

# 5 Handling vertices with a dense neighbourhood

In the short proof of Theorem 1.1 due to King and Reed [24], Theorem 3.1 handles the case of graphs in which every vertex has a sparse neighbourhood. The following result handles the remaining case, that is graphs admitting a vertex with a dense neighbourhood.

**THEOREM 5.1. (KING AND REED [24])** Let $a$ and $\varepsilon$ be constants satisfying $0 < \varepsilon < \frac{1}{6} - 2\sqrt{a}$. Let $G$ be a graph with maximum degree $\Delta$ satisfying $\omega(G) \le \frac{2}{3}(\Delta + 1)$ and let $v$ be such that $m(v) > (1 - a)\binom{n}{2}$. Then

$$ \chi(G) \le \max(\chi(G - v), (1 - \varepsilon)(\Delta + 1)). $$
The goal of this section is to prove Theorem 1.6, which is the immediate analogue of Theorem 5.1 for digraphs. We first recall it here for convenience.

**THEOREM 5.2.** Let $a$ and $\varepsilon$ be constants satisfying $0 < \varepsilon \le \frac{1}{6} - 4\sqrt{a}$. There exists $\Delta(a) \ge 1$ such that the following holds. Let $D$ be a digraph with maximum degree $\Delta_{\max}(D) = \Delta \ge \Delta(a)$ satisfying $\overleftrightarrow{\omega}(D) \le \frac{2}{3}(\Delta + 1)$ and let $v \in V(D)$ be such that $\max(m^-(v), m^+(v)) > (1 - a)\Delta(\Delta - 1)$. Then

$$ \vec{\chi}(D) \le \max(\vec{\chi}(D - v), (1 - \varepsilon)(\Delta + 1)). $$

We will use the following classical result due to Erdős, Rubin, and Taylor [14].

**LEMMA 5.1.** (ERDŐS et al. [14]) Let $G$ be a graph obtained from $K_n$ by removing a matching of size $p$. Then $G$ is $(n-p)$-choosable.

The following is an immediate consequence of Lemma 5.1. A matching in a digraph is a set of pairwise disjoint arcs.

**LEMMA 5.2.** Let $D$ be a digraph obtained from $\vec{K_n}$ by removing a matching of size $p$. Then $D$ is $(n-p)$-dichoosable.

*Proof.* Let $L$ be any $(n-p)$-list assignment of $D$. By Lemma 5.1, there exists an $L$-colouring $\alpha$ of $S(D)$, because $S(D)$ is obtained from $K_n$ by removing a matching of size $p$. As $D$ is obtained from $\vec{S(D)}$ by adding an acyclic set of arcs, $\alpha$ must be an $L$-dicolouring of $D$. □

We are now ready to prove Theorem 5.2.

*Proof.* We take $\Delta(a) = \max(\frac{1-a}{\sqrt{a-a}}, \frac{1-a}{a})$. By directional duality we assume without loss of generality that $m^+(v) \ge (1-a)\Delta(\Delta - 1)$ and let $N = N^+(v) \cup \{v\}$ and $\bar{N} = V(D) - N$. We assume that $|N| = \Delta + 1$ for otherwise we add new vertices dominated by $v$. We partition $N$ into three parts as follows:

$$ N_1 = \{u \in N \mid |N^+(u) \cap \bar{N}| \ge \frac{\Delta}{2}\}, $$

$$ N_2 = \{u \in (N - N_1) \mid |N^+(u) \cap (\bar{N} \cup N_1)| \ge 2\sqrt{a}\Delta\}, \text{ and} $$

$$ N_3 = N - (N_1 \cup N_2). $$

Observe first that

$$ \Delta^2 \ge \sum_{u \in N - \{v\}} d^+(u) = m^+(v) + |A(N, \bar{N})|. $$

Since $m^+(v) > (1 - a)\Delta(\Delta - 1)$, we obtain

$$ |A(N, \bar{N})| < \Delta^2 - (1 - a)\Delta(\Delta - 1) = a\Delta^2 + (1 - a)\Delta. $$

By definition of $N_1$, this implies

$$ \frac{\Delta}{2} |N_1| < a\Delta^2 + (1 - a)\Delta. $$

Using the fact that $\Delta \ge \Delta(a) \ge \frac{1-a}{\sqrt{a-a}}$, we thus have $|N_1| < 2\sqrt{a}\Delta$. By definition, $v \notin N_1$ as $N^+(v) \subseteq N$. We also have $v \notin N_2$ as $N^+(v) \cap (\bar{N} \cup N_1) = N_1$, and $|N_1| < 2\sqrt{a}\Delta$. We will now bound the size of $N_2$. Recall that every vertex $u \in N_1$ satisfies $2|N^+(u) \cap \bar{N}| \ge \Delta \ge d^-(u)$. We thus have the following.

$$ \begin{aligned} |A(N_2 \cup N_3, \bar{N} \cup N_1)| &= |A(N, \bar{N})| + |A(N_2 \cup N_3, N_1)| - |A(N_1, \bar{N})| \\ &\le |A(N, \bar{N})| + \sum_{u \in N_1} d^-(u) - \sum_{u \in N_1} |N^+(u) \cap \bar{N}| \\ &\le |A(N, \bar{N})| + \sum_{u \in N_1} |N^+(u) \cap \bar{N}| \\ &= |A(N, \bar{N})| + |A(N_1, \bar{N})| \\ &\le 2|A(N, \bar{N})| \\ &< 2a\Delta^2 + 2(1 - a)\Delta. \end{aligned} $$
By definition of $N_2$, this implies

$$2\sqrt{a}\Delta|N_2| < 2a\Delta^2 + 2(1-a)\Delta,$$

which together with $\Delta \ge \Delta(a) \ge \frac{1-a}{a}$ implies $|N_2| < 2\sqrt{a}\Delta$. Let $k = \max(\tilde{\chi}(D - v), \lfloor(1 - \varepsilon)(\Delta + 1)\rfloor)$. Since $v \in N_3$, $D - N_3$ is $k$-dicolourable, as it is a subdigraph of $D - v$. Let $\alpha$ be such a $k$-dicolouring and $L$ be the list assignment of $D[N_3]$ defined as follows

$$L(u) = [k] - \alpha(N^+(u) - N_3).$$

We are now going to prove that $D[N_3]$ is $L$-dicolourable, implying that $D$ has dichromatic number at most $k$ (it is straightforward to check that any $L$-dicolouring of $D[N_3]$ extends $\alpha$ into a dicolouring of $D$). First note that, by construction, every vertex $u \in N_3$ satisfies $|N^+(u) - N_3| < 2\sqrt{a}\Delta + |N_2| < 4\sqrt{a}\Delta$. Hence every vertex $u \in N_3$ satisfies

$$|L(u)| > k - 4\sqrt{a}(\Delta + 1) \ge (1 - \varepsilon)(\Delta + 1) - 1 - 4\sqrt{a}(\Delta + 1) \ge \frac{5}{6}(\Delta + 1) - 1,$$

As $|L(u)|$ is an integer, we thus have $|L(u)| \ge \lfloor\frac{5}{6}(\Delta + 1)\rfloor$. Let $M$ be a maximum matching in $\bar{D}[N_3]$ (the complementary of $D[N_3]$). Let $X$ be the vertices of $N_3$ that are not covered $M$. By definition, $X$ is a biclique of $D$ so $|X| \le \frac{2}{3}(\Delta + 1)$. Note that $|N_3| = 2|M| + |X|$. If $|M| \le \frac{1}{6}(\Delta + 1)$ then $|M| + |X| \le \frac{5}{6}(\Delta + 1)$. If $|M| \ge \frac{1}{6}(\Delta + 1)$ then $|M| + |X| = |N_3| - |M| \le \frac{5}{6}(\Delta + 1)$.

In both cases, we obtain $|M| + |X| \le \frac{5}{6}(\Delta + 1)$. Since $D[N_3]$ is a subdigraph of a digraph obtained from $\overleftarrow{K}_{|N_3|}$ by removing a matching of size $|M|$, $D[N_3]$ is $(|M| + |X|)$-dichosable by Lemma 5.2. Therefore $D[N_3]$ must be $\lfloor\frac{5}{6}(\Delta + 1)\rfloor$-dichosable, so in particular it is $L$-dicolourable, implying the result. □

# 6 Proof of the main result

This section is devoted to the proof of our main result, namely Theorem 1.3. We need the following intermediate result proved by the second author [29]. Recall that an oriented graph is a digraph without any digon.

**THEOREM 6.1.** (PICASARRI-ARRIETA [29]) Let $D$ be an oriented graph, then $\tilde{\chi}(D) \le \max(2, \Delta_{\min}(D))$.

We are now going to prove Theorem 1.3. Let us first restate it.

**THEOREM 6.2.** There exists $\varepsilon > 0$ such that every digraph $D$ satisfies

$$\tilde{\chi}(D) \le \lfloor(1 - \varepsilon)(\tilde{\Delta}(D) + 1) + \varepsilon\overrightarrow{\omega}(D)\rfloor.$$

*Proof.* Let $\Delta_1$ be as in Corollary 3.1 and, for a real number $a > 0$, let $\Delta(a)$ be as in Theorem 5.2. We define $a$, $\varepsilon_0$, $\Delta_2$, $\varepsilon$, and $\gamma_\varepsilon$ as follows:

* $a = \frac{1}{600}$,

* $\varepsilon_0 = \frac{1}{6} - 4\sqrt{a} > 0$,

* $\Delta_2 = \min\{\Delta \in \mathbb{N} | a > \frac{\log^3 \Delta}{\Delta - 1}\}$,

* $\varepsilon = \min\left(\frac{1}{\Delta_1}, \frac{1}{\Delta_2}, \frac{1}{\Delta(a)}, \frac{1}{3}\varepsilon_0, \frac{a}{16e^7}\right)$, and

* $\gamma_\varepsilon = \frac{\varepsilon}{1 - \varepsilon} \le 2\varepsilon$.

We claim that the statement holds for this specific value of $\varepsilon$. Assume this is not the case, and let $D$ be a counterexample with minimum order. For the sake of conciseness let us denote $\tilde{\Delta}(D)$ by $\tilde{\Delta}$, $\Delta_{\max}(D)$ by $\Delta_{\max}$, $\overrightarrow{\omega}(D)$ by $\overrightarrow{\omega}$, and let $k = \lfloor(1 - \varepsilon)(\tilde{\Delta} + 1) + \varepsilon\overrightarrow{\omega}\rfloor$. As $D$ is a minimum counter example, it satisfies $\tilde{\chi}(D) > k$ and for every vertex $v \in V$ we have $\tilde{\chi}(D - v) \le k$. This directly implies that every vertex $v$ of $D$ satisfies $\min(d^-(v), d^+(v)) \ge k$, for otherwise a $k$-dicolouring of $D$ can be obtained from any $k$-dicolouring of $D - v$ by choosing for $v$ a colour that is not appearing either in its in-neighbourhood or in its out-neighbourhood. In particular, this implies that $\tilde{\Delta}$ must be close to $\Delta_{\max}$, as we justify in the following claim.

**CLAIM 6.1.** $\Delta_{\max} \le (1 + \gamma_\varepsilon)\tilde{\Delta}$.
*Proof of claim.* Assume this is not the case, so there exists a vertex $v$ such that $\max(d^+(v), d^-(v)) > (1 + \gamma_\epsilon)\tilde{\Delta}$. By directional duality, we assume without loss of generality that $d^+(v) \ge d^-(v)$. Therefore, we have $\tilde{\Delta}^2 \ge d^+(v) \cdot d^-(v) > (1 + \gamma_\epsilon)\tilde{\Delta} \cdot d^-(v)$, which implies $d^-(v) < \frac{1}{1+\gamma_\epsilon}\tilde{\Delta} = (1 - \epsilon)\tilde{\Delta} \le k$, a contradiction. ◇

With Theorem 1.5 in hands, we can also justify that there exists a significant gap between $\vec{\omega}$ and $\Delta_{\max}$.

CLAIM 6.2. $\vec{\omega} \le \frac{2}{3}(\Delta_{\max} + 1)$.

*Proof of claim.* Assume for a contradiction that $\vec{\omega} > \frac{2}{3}(\Delta_{\max} + 1)$. By Theorem 1.5, there exists an acyclic set of vertices $I \subseteq V(D)$ which intersects every maximum biclique of $D$. Among all such sets $I$, we choose one with maximum size. In particular, this implies that every vertex in $V(D) - I$ has at least one in-neighbour and one out-neighbour in $I$. Let $D'$ be $D - I$. As $I$ is acyclic and intersects every maximum clique of $D$, we have $\vec{\omega}(D') = \vec{\omega} - 1$. The following shows that we also have $\tilde{\Delta}(D') \le \tilde{\Delta} - 1$.

$$ 
\begin{aligned}
\tilde{\Delta}(D') &= \max \left\{ \sqrt{d_{D'}^{+}(v) \cdot d_{D'}^{-}(v)} \mid v \in V(D') \right\} \\
&\le \max \left\{ \sqrt{(d_{D}^{+}(v) - 1)(d_{D}^{-}(v) - 1)} \mid v \in V(D') \right\} \\
&\le \max \left\{ \sqrt{d_{D}^{+}(v)d_{D}^{-}(v)} - 1 \mid v \in V(D') \right\} \\
&\le \tilde{\Delta} - 1,
\end{aligned}
$$

where in the first inequality we used the maximality of $I$ and in the second inequality we used that $\sqrt{(p-1)(q-1)} \le \sqrt{pq} - 1$ holds for every pair of real numbers $p, q \ge 1$. We briefly justify it here for completeness.

$$ 
\begin{aligned}
0 &\le (\sqrt{p} - \sqrt{q})^2 \\
&\Rightarrow -p - q \le -2\sqrt{pq} \\
&\Rightarrow pq - p - q + 1 \le pq - 2\sqrt{pq} + 1 \\
&\Rightarrow (p-1)(q-1) \le (\sqrt{pq} - 1)^2 \\
&\Rightarrow \sqrt{(p-1)(q-1)} \le \sqrt{pq} - 1
\end{aligned}
$$

Since $I$ is acyclic, we have $\vec{\chi}(D) \le \vec{\chi}(D') + 1$, as any dicolouring of $D'$ can be extended to $D$ by colouring $I$ with an additional colour. Together with the minimality of $D$ we obtain

$$ 
\begin{aligned}
\vec{\chi}(D) &\le \left[ (1 - \varepsilon)(\tilde{\Delta}(D') + 1) + \varepsilon\vec{\omega}(D') \right] + 1 \\
&\le \left[ (1 - \varepsilon)\tilde{\Delta} + \varepsilon(\vec{\omega} - 1) \right] + 1 \\
&= \left[ (1 - \varepsilon)(\tilde{\Delta} + 1) - (1 - \varepsilon) + \varepsilon\vec{\omega} - \varepsilon + 1 \right] = k,
\end{aligned}
$$

a contradiction. ◇

We finally claim that $\tilde{\Delta}$ is large enough.

CLAIM 6.3. $\Delta_{\max} \ge \tilde{\Delta} \ge \max(\Delta_1, \Delta_2, \Delta(a))$.

*Proof of claim.* It is clear from the definitions that $\Delta_{\max} \ge \tilde{\Delta}$. Assume for a contradiction that $\tilde{\Delta} < \max(\Delta_1, \Delta_2, \Delta(a))$. Since $\varepsilon \le \min(\frac{1}{\tilde{\Delta}_1}, \frac{1}{\tilde{\Delta}_2}, \frac{1}{\tilde{\Delta}(a)})$ we have $\varepsilon < \frac{1}{\tilde{\Delta}}$, which implies:

$$ k = \left[ \tilde{\Delta} + 1 + \varepsilon(\vec{\omega} - \tilde{\Delta} - 1) \right] \ge \left[ \tilde{\Delta} + \frac{1}{\tilde{\Delta}}(\vec{\omega} - 1) \right]. $$

Using the facts that $\vec{\chi}(D) > k$ and that $\vec{\chi}(D) \le \lfloor \tilde{\Delta} + 1 \rfloor$, we deduce

$$ \lfloor \tilde{\Delta} + 1 \rfloor > \lfloor \tilde{\Delta} + \frac{1}{\tilde{\Delta}}(\vec{\omega} - 1) \rfloor. $$
This is a contradiction unless $\vec{\omega} = 1$ and $\tilde{\Delta}$ is an integer. Henceforth we assume that $\vec{\omega} = 1$, i.e. $D$ is an oriented graph, and $\tilde{\Delta} \in \mathbb{N}$. In particular, we have $k \ge \tilde{\Delta}$. As $D$ is an oriented graph, by Theorem 6.1 we must have $\Delta_{\min}(D) \le 1$, for otherwise $\vec{\chi}(D) \le \Delta_{\min}(D) \le \tilde{\Delta} \le k$, a contradiction. Hence we have $\tilde{\Delta}(D) \le 1$, for otherwise $\vec{\chi}(D) \le 2 \le \tilde{\Delta} \le k$, a contradiction. If $\tilde{\Delta} = 1$ then $k = [2 - \varepsilon] = 2$. If $\tilde{\Delta} = 0$ then $k = 1$. Both cases yield a contradiction, which concludes the proof of the claim. ◇

We now distinguish two cases, depending on the sparseness of $D$.

**Case 1:** There exists a vertex $v$ such that $\max(m^-(v), m^+(v)) \ge (1 - a)\Delta(\Delta - 1)$.

By Claim 6.2 we have $\vec{\omega} \le \frac{2}{3}(\Delta_{\max} + 1)$. As $\varepsilon_0 = \frac{1}{6} - 4\sqrt{a}$, by Theorem 5.2 we have

$$ \vec{\chi}(D) \le \max(\vec{\chi}(D - v), (1 - \varepsilon_0)(\Delta_{\max} + 1)). $$

Recall that $\vec{\chi}(D - v) \le k$ as $D$ is a minimum counterexample. Since $\vec{\chi}(D) > k$, we thus necessarily have

$$ \vec{\chi}(D) \le (1 - \varepsilon_0)(\Delta_{\max} + 1) \le (1 - \varepsilon_0)(1 + \gamma_{\varepsilon})(\tilde{\Delta} + 1) \le (1 - \varepsilon)(\tilde{\Delta} + 1), $$

where in the second inequality we used Claim 6.1, and in the last inequality we used $\varepsilon \le \varepsilon_0 - \gamma_{\varepsilon}$, which holds because $\gamma_{\varepsilon} \le 2\varepsilon$ and $\varepsilon \le \frac{1}{3}\varepsilon_0$. This yields the contradiction as $(1 - \varepsilon)(\tilde{\Delta} + 1) \le k$.

**Case 2:** For every vertex $v \in V(D)$ we have $\max(m^-(v), m^+(v)) \le (1 - a)\Delta(\Delta - 1)$.

A fortiori every vertex satisfies $\min(m^-(v), m^+(v)) \le (1 - a)\Delta(\Delta - 1)$. By Claim 6.3 we know that $\Delta_{\max} \ge \max(\Delta_1, \Delta_2)$. Hence, by definition of $\Delta_2$, we have $a > \frac{\log^3 \Delta}{\Delta - 1}$. We can thus apply Corollary 3.1, which together with Claim 6.1 gives

$$ \vec{\chi}(D) \le \left(1 - \frac{a}{5e^7}\right) (\Delta_{\max} + 1) \le \left(1 - \frac{a}{5e^7}\right) (1 + \gamma_{\varepsilon})(\tilde{\Delta} + 1) \le (1 - \varepsilon)(\tilde{\Delta} + 1). $$

where in the last inequality we used $\varepsilon \le \frac{a}{5e^7} - \gamma_{\varepsilon}$, which holds because $\gamma_{\varepsilon} \le 2\varepsilon$ and $\varepsilon \le \frac{a}{15e^7}$. This contradicts $\vec{\chi}(D) > k$.

Since one of the two cases above occurs, and because each of them yields a contradiction, the result follows. □

## 7 Further research: analogues for $\Delta_{\min}$

In this work we proved an analogue of Reed's result for digraphs by taking the maximum degree of a digraph to be $\tilde{\Delta}$. A natural question then arises: can we strengthen this result by replacing $\tilde{\Delta}$ with $\Delta_{\min}$? The answer to this question turns out to be negative. Moreover, for every fixed real numbers $\varepsilon, \varepsilon'$ with $0 < \varepsilon' < 2\varepsilon$, there exists a digraph $D$ with

$$ \vec{\chi}(D) > \left[ (1 - \varepsilon)(\Delta_{\min}(D) + 1) + \varepsilon' \vec{\omega}(D) \right]. $$

This is because the $k$-DICOLOURABILITY problem is NP-complete for every fixed $k \ge 2$, even when restricted to digraphs $D$ satisfying $\Delta_{\min}(D) = k$ and $\vec{\omega}(D) = \left\lceil \frac{k+1}{2} \right\rceil$, as shown in [29]. In particular, the reduction shows that there exist such digraphs satisfying $\vec{\chi}(D) = k + 1$. Hence, if we choose $k$ to be at least $\frac{2\varepsilon' - 2\varepsilon}{2\varepsilon - \varepsilon'}$, we deduce the existence of digraphs $D$ with $\Delta_{\min}(D) = k$, $\vec{\omega}(D) = \left\lceil \frac{k+1}{2} \right\rceil$, and $\vec{\chi}(D) = k + 1$, while $\left\lceil (1 - \varepsilon)(k + 1) + \varepsilon' \left\lceil \frac{k+1}{2} \right\rceil \right\rceil \le k$.

However, we believe that an analogue of our result holds with $\Delta_{\min}$ instead of $\tilde{\Delta}$ if we also adapt the notion of clique number. Given a digraph $D$, a directed clique of $D$ is a set of vertices $X$ that can be partitioned into $(X_1, X_2)$ such that both $D[X_1]$ and $D[X_2]$ are complete digraphs, and $D$ contains every possible arc $uv$ with $u \in X_1$ and $v \in X_2$. The directed clique number of $D$, denoted by $\vec{\omega}(D)$, is the size of a largest directed clique of $D$. We propose the following conjecture.

**CONJECTURE 7.1.** There exists $\varepsilon > 0$ such that every digraph $D$ satisfies

$$ \vec{\chi}(D) \le \left\lceil (1 - \varepsilon)\Delta_{\min}(D) + \varepsilon\vec{\omega}(D) \right\rceil. $$

In particular, the conjecture above implies the following slightly weaker one, which if true shows that the condition $\varepsilon' < 2\varepsilon$ mentioned above is indeed necessary.
**CONJECTURE 7.2.** There exists $\varepsilon > 0$ such that every digraph $D$ satisfies

$$ \vec{\chi}(D) \le \left[ (1 - \varepsilon)\Delta_{\min}(D) + 2\varepsilon\vec{\omega}(D) \right]. $$

We are inclined to believe that these two conjectures are true even for $\varepsilon = \frac{1}{2}$. One direction for proving Conjecture 7.1 would be to prove an analogue of Theorem 1.3 using the maximum out-degree $\Delta^+$ instead of $\vec{\Delta}$, that is to prove the existence of $\varepsilon > 0$ such that every digraph $D$ satisfies $\vec{\chi}(D) \le [(1 - \varepsilon)(\Delta^+(D) + 1) + \varepsilon\vec{\omega}(D)]$, where $\Delta^+(D) = \max\{d^+(v) | v \in V(D)\}$. It is of interest that already the case of oriented graphs is open.

**PROBLEM 7.1.** Show the existence of $\varepsilon > 0$ such that every oriented graph $D$ with sufficiently large maximum out-degree $\Delta^+(D)$ satisfies $\vec{\chi}(D) \le (1 - \varepsilon)\Delta^+(D)$.

The hardness of this problem mainly comes from the fact that the maximum in-degree of a digraph can be arbitrarily larger than its maximum out-degree. Hence, the proof of Theorem 3.2 cannot be directly adapted as we cannot bound the degree of dependence of bad events when applying the Lovász Local Lemma.

## References

[1] P. Aboulker and G. Aubian. *Four proofs of the Directed Brooks' Theorem*. Discrete Math., page 113193, 2022.

[2] P. Aboulker, G. Aubian, and P. Charbit. *Digraph colouring and arc-connectivity*. preprint arXiv:2304.04690, 2023.

[3] P. Aboulker, G. Aubian, P. Charbit, and S. Thomassé. (*P6*, triangle)-free digraphs have bounded dichromatic number. preprint arXiv:2212.02272, 2022.

[4] P. Aboulker, P. Charbit, and R. Naserasr. *Extension of Gyárfás-Sumner conjecture to digraphs*. Electron. J. Comb., 28(P2.27), 2021.

[5] N. Alon and J. H. Spencer. *The probabilistic method*. Wiley Series in Discrete Mathematics and Optimization. Wiley-Blackwell, Hoboken, NJ, 3 edition, Aug. 2008.

[6] S. D. Andres and W. Hochstättler. *Perfect digraphs*. J. Graph Theory, 79(1):21–29, 2015.

[7] J. Bang-Jensen and G. Z. Gutin. *Digraphs: Theory, Algorithms and Applications*. Springer-Verlag, London, 2nd edition, 2009.

[8] D. Bokal, G. Fijavz, M. Juvan, P. M. Kayll, and B. Mohar. *The circular chromatic number of a digraph*. J. Graph Theory, 46(3):227–240, 2004.

[9] M. Bonamy, T. Perrett, and L. Postle. *Colouring graphs with sparse neighbourhoods: Bounds and applications*. J. Comb. Theory, Ser. B, 155:278–317, 2022.

[10] L. Cook, T. Masařík, M. Pilipczuk, A. Reinald, and U. S. Souza. *Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$*. Electron. J. Comb., 30(P3.36), 2023.

[11] M. Delcourt and L. Postle. *On the list coloring version of Reed's conjecture*. Electron. Notes Discret. Math., 61:343–349, 2017.

[12] P. Erdős. *Problems and results in number theory and graph theory*. In Proc. Ninth Manitoba Conference on Numerical Math. and Computing, pages 3–21, 1979.

[13] P. Erdős and L. Lovász. *Problems and results on 3-chromatic hypergraphs and some related questions*. Infinite and Finite Sets, 10(2):609–627, 1975.

[14] P. Erdős, A. L. Rubin, and H. Taylor. *Choosability in graphs*. Congr. Numer., 26(4):125–157, 1979.

[15] N. Golowich. *The m-degenerate chromatic number of a digraph*. Discrete Math., 339(6):1734–1743, 2016.

[16] D. Gonçalves, L. Picasarri-Arrieta, and A. Reinald. *Brooks-type colourings of digraphs in linear time*. preprint arXiv:2405.05222, 2024.

[17] A. Hajnal. *A theorem on k-saturated graphs*. Canadian J. Math., 17:720–724, 1965.

[18] A. Harutyunyan and B. Mohar. *Gallai's theorem for list coloring of digraphs*. SIAM J. Discrete Math., 25(1):170–180, 2011.

[19] A. Harutyunyan and B. Mohar. *Strengthened Brooks' theorem for digraphs of girth at least three*. Electron. J. Comb., 18(P195), 2011.

[20] P. E. Haxell. *A note on vertex list colouring*. Comb. Probab. Comput., 10(4):345–347, 2001.

[21] E. Hurley, R. de Joannis de Verclos, and R. J. Kang. *An improved procedure for colouring graphs of bounded local density*. Adv. Comb., 2022.

[22] T. Kelly and L. Postle. *A local epsilon version of Reed's Conjecture*. J. Comb. Theory, Ser. B, 141:181–222, 2020.

[23] A. D. King. *Hitting all maximum cliques with a stable set using lopsided independent transversals*. J. Graph Theory, 67(4):300–305, 2011.
[24] A. D. King and B. A. Reed. *A short proof that $\chi$ can be bounded $\varepsilon$ away from $\Delta + 1$ toward $\omega$. J. Graph Theory*, 81(1):30–34, Jan. 2015.

[25] A. V. Kostochka. *Degree, density and chromatic number of graphs*. Metody Diskret. Analiz., 35:45–70, 1980.

[26] B. Mohar. *Circular colorings of edge-weighted graphs*. J. Graph Theory, 43(2):107–116, 2003.

[27] M. Molloy and B. A. Reed. *Graph colouring and the probabilistic method*. Algorithms and Combinatorics. Springer, Berlin, Germany, Nov. 2001.

[28] V. Neumann-Lara. *The dichromatic number of a digraph*. J. Comb. Theory, Ser. B, 33:265–270, 1982.

[29] L. Picasarri-Arrieta. *Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring*. J. Graph Theory, 106(1):5–22, 2024.

[30] L. Rabern. *On hitting all maximum cliques with an independent set*. J. Graph Theory, 66(1):32–37, 2011.

[31] B. A. Reed. $\omega$, $\Delta$, and $\chi$. J. Graph Theory, 27(4):177–212, 1998.

[32] M. Stiebitz, T. Schweser, and B. Toft. *Brooks’ Theorem: Graph Coloring and Critical Graphs*. Springer Nature Switzerland, 2024.

[33] M. Talagrand. *Concentration of measure and isoperimetric inequalities in product spaces*. Publ. Math. Inst. Hautes Études Sci., 81:73–205, 1995.