# Subdivisions in dicritical digraphs with large order or digirth*

Lucas Picasarri-Arrieta and Clément Rambaud

Université Côte d'Azur, CNRS, Inria, I3S, Sophia-Antipolis, France

[lucas.picasarri-arrieta, clement.rambaud]@inria.fr

## Abstract

Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of a partition of its vertex set into acyclic induced subgraphs. A digraph is dicritical if the removal of any arc or vertex decreases its dichromatic number. In this paper we give sufficient conditions on a dicritical digraph of large order or large directed girth to contain a given digraph as a subdivision. In particular, we prove that (i) for every integers $k, \ell$, large enough dicritical digraphs with dichromatic number $k$ contain an orientation of a cycle with at least $\ell$ vertices; (ii) there are functions $f, g$ such that for every subdivision $F^*$ of a digraph $F$, digraphs with directed girth at least $f(F^*)$ and dichromatic number at least $g(F)$ contain a subdivision of $F^*$, and if $F$ is a tree, then $g(F) = |V(F)|$; (iii) there is a function $f$ such that for every subdivision $F^*$ of $TT_3$ (the transitive tournament on three vertices), digraphs with directed girth at least $f(F^*)$ and minimum out-degree at least 2 contain $F^*$ as a subdivision.

**Keywords:** Digraphs, dichromatic number, dicritical digraphs, subdivisions, digirth.

## 1 Introduction

Let $D$ be a digraph. A $k$-colouring of $D$ is a function $\phi: V(D) \to [k]$. It is a $k$-dicolouring if no directed cycle $C$ in $D$ is monochromatic for $\phi$ (that is $|\phi(V(C))| > 1$). Equivalently, it is a $k$-dicolouring if every colour class induces an acyclic subdigraph. The smallest integer $k$ such that $D$ has a $k$-dicolouring is the *dichromatic number* of $D$ and is denoted by $\vec{\chi}(D)$. A digraph $D$ is $k$-dicritical if $\vec{\chi}(D) = k$ and every proper subdigraph $H$ of $D$ satisfies $\vec{\chi}(H) < k$. The following is a central result when dealing with substructures in digraphs of large dichromatic number.

**Theorem 1** (Aboulker et al. [1]). Let $F$ be a digraph on $n$ vertices, $m$ arcs and $c$ connected components. Every digraph $D$ satisfying $\vec{\chi}(D) \ge 4^{m-n+c}(n-1) + 1$ contains a subdivision of $F$.

For every digraph $F$, we denote by $\text{mader}_{\vec{\chi}}(F)$ the least integer $c_F$ for which every digraph $D$ either contains a subdivision of $F$ or has dichromatic number at most $c_F - 1$. Note that $\text{mader}_{\vec{\chi}}(F)$ is well-defined by Theorem 1. The result above was generalized in a recent work of Steiner [21] (see also [15]) who extended it to subdivisions with modular constraints.

Since every digraph is a subdigraph of $\vec{K}_n$, the complete digraph on $n$ vertices, it is natural to look for the value of $\text{mader}_{\vec{\chi}}(\vec{K}_n)$. The result above implies that $\text{mader}_{\vec{\chi}}(\vec{K}_n) \le 4^{n^2-2n+1}$. A more precise computation using the tools developed in [1] yields the following best known upper bound, whose proof is presented in Section 2.

**Proposition 2.** $\text{mader}_{\vec{\chi}}(\vec{K}_n) \le 4^{\frac{2}{3}n^2+2n-\frac{8}{3}}$.

For every digraph $F$ on $n$ vertices, we have $\text{mader}_{\vec{\chi}}(F) \ge n$. This is because $\vec{K}_{n-1}$, the complete digraph on $n-1$ vertices, has dichromatic number $n-1$ and does not contains any subdivision of $F$.

<footnote>*Research supported by the research grant DIGRAPHS ANR-19-CE48-0013 and by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE-0004.</footnote>
For some digraphs $F$, it then appears that the value of $\mathrm{mader}_{\chi}(F)$ does not capture the structure of $F$
but only its order. For instance, $\mathrm{mader}_{\vec{\chi}}(\vec{C}_n) \ge n$, but every 2-dicritical digraph on at least $n$ vertices
actually contains a subdivision of $\vec{C}_n$. In order to have a better understanding of digraphs forced to
contain subdivisions of $F$, one may then ask for the minimum $k$ such that there is a finite number of
$k$-dicritical digraphs which do not contain any subdivision of $F$. The following question then naturally
arises.

**Question 3.** Let $F^*$ be a subdivision of a digraph $F$. Is it true that the set of $(\mathrm{mader}_{\chi}(F))$-dicritical digraphs that do not contain any subdivision of $F^*$ is finite ?

Unfortunately, the answer to this question is negative. To see that, consider for every positive integers $k$ and $\ell$ the digraph $C(k, \ell)$, which is the union of two internally disjoint directed paths from a vertex $x$ to a vertex $y$ of lengths respectively $k$ and $\ell$. Observe that $\mathrm{mader}_{\chi}(C(1, 2)) = 3$ because $\overrightarrow{K_2}$ does not contain any subdivision of $C(1, 2)$ and every 3-dicritical digraph is 2-arc-strong. The following answers Question 3 by the negative for $F = C(1, 2)$ and $F^* = C(3, 3)$.

**Proposition 4.** For every integer $n \ge 3$, there exists a 3-dicritical digraph $D_n$ on $n$ vertices that does not contain any subdivision of $C(3, 3)$.

*Proof.* Let $D_n$ be the digraph obtained from a directed cycle on $n-1$ vertices $\vec{C}_{n-1}$ by adding a new vertex $x$ and all possible digons between $x$ and $V(\vec{C}_{n-1})$ (see Figure 1 for an illustration). This digraph is 3-dicritical (it follows from Lemma 17 and the fact that directed cycles are 2-dicritical) and does not contain any subdivision of $C(3, 3)$. $\square$

<figure><img src="image_1.png" /><figcaption>Figure 1: The digraph $D_{10}$.</figcaption></figure>

In Section 3, we show that the answer to Question 3 is actually negative not only for $C(1, 2)$ but
for every digraph $F$ on at least three vertices with at least one arc. Let $F$ be such a digraph and $F^*$
be a subdivision of $F$ in which an arc has been subdivided at least $3 \cdot \mathrm{mader}_{\chi}(F) + 1$ times. Since
$\mathrm{mader}_{\chi}(F) \ge |V(F)| \ge 3$, the following result implies that the set of $(\mathrm{mader}_{\chi}(F))$-dicritical digraphs
that do not contain any subdivision of $F^*$ is infinite.

**Theorem 5.** For every integer $k \ge 3$, there are infinitely many $k$-dicritical digraphs without any directed path on $3k + 1$ vertices.

Theorem 5 establishes a distinction between the directed and undirected cases. In the undirected case, for every fixed $k \ge 3$, there exists a non-decreasing function $f_k: \mathbb{N} \to \mathbb{N}$ such that every $k$-critical graph on at least $f_k(\ell)$ vertices contains a path on $\ell$ vertices. This was first proved by Kelly and Kelly [13] in 1954, answering a question of Dirac. The bound on $f_k$ was then improved by Alon, Krivelevich and Seymour [2] and finally settled by Shapira and Thomas [20], who proved that the largest cycle in a $k$-critical graph on $n$ vertices has length at least $c_k \cdot \log(n)$, where $c_k$ is a constant depending only on $k$. This bound is best possible up to the multiplicative constant $c_k$, as shown by a construction of Gallai [9, 10] (see [20]).

On the positive side, we adapt the proof of Alon et al. [2] and show that, in $k$-dicritical digraphs,
the length of the longest oriented cycle (i.e. the longest cycle in the underlying graph) grows with the
number of vertices, and so does the length of its longest oriented path (i.e. the longest path in the underlying graph).

**Theorem 6.** For every fixed integers $k \ge 2$ and $\ell \ge 3$, there are finitely many $k$-dicritical digraphs with no oriented cycle on at least $\ell$ vertices.

Since Question 3 turns out to be almost always false, we propose as an alternative to restrict to digraphs with large girth. The *girth* of a graph $G$, denoted by $girth(G)$, is the length of a smallest cycle in $G$, with the convention $girth(G) = +\infty$ if $G$ is a forest. The girth of a digraph $D$, denoted by $girth(D)$, is $girth(UG(D))$. The *digirth* of a digraph is the length of its shortest directed cycle. By convention we have $girth(D) = +\infty$ if $D$ is acyclic. A celebrated result of Erdős (see [3]) states that there exist graphs of arbitrarily large chromatic number and arbitrarily large girth. It has been generalised by Bokal et al. [6] who showed the existence of digraphs of arbitrarily large girth and dichromatic number. For every integer $g$, we denote by $\text{mader}_{\vec{\chi}}^{(g)}(F)$ the least integer $k$ such that every digraph $D$ satisfying $\vec{\chi}(D) \ge k$ and $girth(D) \ge g$ contains a subdivision of $F$. Note that $\text{mader}_{\vec{\chi}}(F) = \text{mader}_{\vec{\chi}}^{(2)}(F)$ and that $\text{mader}_{\vec{\chi}}^{(g)}(F)$ is non-increasing in $g$. We conjecture that the analogue of Question 3 for digraphs of large girth is actually true.

**Conjecture 7.** For every digraph $F$ and every subdivision $F^*$ of $F$, there exists $g$ such that $\text{mader}_{\vec{\chi}}^{(g)}(F^*) \le \text{mader}_{\vec{\chi}}(F)$.

This conjecture seems to be hard to prove since the exact value of $\text{mader}_{\vec{\chi}}(F)$ is known for very few classes of digraphs. In order to provide some support to this conjecture, in Section 4 we show that the value of $\text{mader}_{\vec{\chi}}^{(g)}(F^*)$ depends only on $F$ when $g$ is large enough. Our proof is strongly based on the key-lemma of [1].

**Theorem 8.** Let $k \ge 1$ be an integer. For every non-empty digraph $F$, if $F^*$ is obtained from $F$ by subdividing every arc at most $k-1$ times, then $\text{mader}_{\vec{\chi}}^{(k)}(F^*) \le \frac{1}{3}(4^{m(F)+1}n(F)-1)$.

In Section 5, we prove that Conjecture 7 holds for every digraph $F$ whose underlying undirected graph $UG(F)$ is a forest.

**Theorem 9.** Let $k \ge 1$ be an integer and let $T$ be a bidirected tree. If $T^*$ is obtained from $T$ by subdividing every arc at most $k-1$ times, then $\text{mader}_{\vec{\chi}}^{(2k)}(T^*) \le \text{mader}_{\vec{\chi}}(T) = n(T)$.

In the case of oriented trees, we improve Theorem 9 as follows.

**Theorem 10.** Let $k \ge 1$ be an integer. Let $D$ be a digraph, $T$ be an oriented tree and $T^*$ obtained from $T$ by subdividing every arc at most $k-1$ times. If $\vec{\chi}(D) \ge \text{mader}_{\vec{\chi}}(T)$ and $girth(D) \ge k$, then $D$ contains $T^*$ as a subdigraph.

Observe that every digraph $D$ contains a subdigraph $H$ such that $\delta^+(H) \ge \vec{\chi}(D)-1$ (by taking $H$ a $\vec{\chi}(D)$-dicritical subdigraph of $D$). Hence, for every integer $k$, if a digraph $F$ is such that every digraph $D$ with $\delta^+(D) \ge k-1$ contains a subdivision of $F$, then $\text{mader}_{\vec{\chi}}(F) \le k$. In Section 6, we look for similar results using $\delta^+$ instead of $\vec{\chi}$. Conjecture 7 for $F = C(1,2)$ appears to be a consequence of the following theorem (recall that $\text{mader}_{\vec{\chi}}(C(1,2)) = 3$).

**Theorem 11.** For every integer $k \ge 2$, every digraph $D$ with $\delta^+(D) \ge 2$ and $girth(D) \ge 8k-6$ contains a subdivision of $C(k,k)$.

An *oriented graph* is a digraph with girth at least 3. When $k=2$, we improve Theorem 11 as follows.

**Theorem 12.** Every oriented graph $D$ with $\delta^+(D) \ge 2$ contains a subdivision of $C(2,2)$.

We also consider out-stars. For integers $k, \ell$, let $S_k^{+(\ell)}$ be the digraph consisting in $k$ directed paths of length $\ell$ sharing their origin (and no other common vertices). The *centre* of $S_k^{+(\ell)}$ is its unique source.

**Theorem 13.** For every positive integers $k, \ell$, every digraph with $\delta^+(D) \ge k$ and $girth(D) \ge \frac{k\ell-1}{k-1}+1$ contains a copy of $S_k^{+(\ell)}$ with centre $u$ for every chosen vertex $u$.
When $k = 2$, Theorem 13 can be improved by reducing the bound on digirth($D$) down to $2\ell$.

**Theorem 14.** Let $D$ be a digraph with $\delta^+(D) \ge 2$. If digirth($D$) $\ge 2\ell$, then $D$ contains a copy of $S_2^{+(\ell)}$.

We conclude in Section 7 by some open problems and further research directions.

## Notations

We refer the reader to [4] for notation and terminology not explicitly defined in this paper.

Given a digraph $D$ (resp. a graph $G$), we denote by $V(D)$ (resp. $V(G)$) its set of vertices and $A(D)$ (resp. $E(G)$) its set of arcs (resp. set of edges). For every vertex $v \in V(D)$, $N^+(v)$, $N^-(v)$ denote respectively the in-neighbourhood and the out-neighbourhood of $v$ in $D$, $d^+(v) = |N^+(v)|$, $d^-(v) = |N^-(v)|$, and $d(v) = d^+(v) + d^-(v)$. Moreover, for every set $A$ of vertices, we write $N^+(A) = \bigcup_{a \in A} N^+(a)$, $N^-(A) = \bigcup_{a \in A} N^-(a)$ and $N(A) = N^+(A) \cup N^-(A)$. We also define $\delta^+(D) = \min_{v \in V(D)} d^+(v)$, $\delta^-(D) = \min_{v \in V(D)} d^-(v)$, and $\delta(D) = \min_{v \in V(D)} d(v)$. Similarly $\Delta^+(D) = \max_{v \in V(D)} d^+(v)$, $\Delta^-(D) = \max_{v \in V(D)} d^-(v)$.

A *digon* in $D$ is a pair of opposite arcs between two vertices. Such a pair of arcs $\{uv, vu\}$ is denoted by $[u, v]$. The *underlying graph* of a digraph $D$, denoted by $UG(D)$, is the undirected graph on the same vertex set which contains an edge linking two vertices if $D$ contains at least one arc linking these two vertices. An *oriented graph* is a digraph with digirth at least 3. A *bidirected digraph* is any digraph $D$ such that for every $x, y \in V(D)$, $xy \in A(D) \Leftrightarrow yx \in A(D)$, and we write $D = \overrightarrow{G}$ where $G = UG(D)$. An *oriented cycle* (resp. *oriented path*) is an oriented graph whose underlying graph is a cycle (resp. path). A *directed cycle* is an oriented cycle in which every vertex has in- and out-degree 1. A *directed path* is obtained from a directed cycle by removing a vertex. The *directed cycle* on $n$ vertices and the directed path on $n$ vertices are respectively denoted by $\overrightarrow{C_n}$ and $\overrightarrow{P_n}$. The lengths of $\overrightarrow{P_n}$ and $\overrightarrow{C_n}$ are respectively $n-1$ and $n$. An *antidirected path* is an orientation of a path where every vertex $v$ satisfies $\min(d^+(v), d^-(v)) = 0$.

If $u$ is a vertex of a digraph $D$ with $d^-(u) = 1$, we define the *predecessor* of $u$ in $D$, denoted by $pred_D(u)$, as the unique in-neighbour of $u$ in $D$. Similarly, if $d^+(u) = 1$, we define the *successor* of $u$ in $D$, denoted by $succ_D(u)$, as the unique out-neighbour of $u$ in $D$.

Given two vertices $a, b$ in a directed cycle $C$ (with possibly $a = b$), we denote by $C[a, b]$ the directed path from $a$ to $b$ along $C$ (which is the single-vertex path when $a = b$). Moreover, we define $C[a, b[ = C[a, b] - b$, $C[a, b] = C[a, b] - a$, and $C[a, b[ = C[a, b] - \{a, b\}$. Note that these subpaths may be empty. Given a directed path $P$ and two vertices $a, b$ in $V(P)$, we use similar notations $P[a, b]$, $P[a, b[, P[a, b]$ and $P[a, b[$. We denote by $init(P)$ the first vertex of $P$ (i.e. the unique vertex with in-degree 0) and $term(P)$ its last one. Given two directed paths $P, Q$ such that $V(P) \cap V(Q) = \{x\}$ where $x = term(P) = init(Q)$, the *concatenation* of $P$ and $Q$, denoted by $P \cdot Q$, is the digraph $(V(P) \cup V(Q), A(P) \cup A(Q))$. The vertices in $V(P) \setminus \{init(P), term(P)\}$ are called the *internal vertices* of $P$. If $U$ and $V$ are two sets of vertices in $D$, then a $(U, V)$-path in $D$ is a directed path $P$ in $D$ with $init(P) \in U$ and $term(P) \in V$, and we also say that $P$ is a directed path from $U$ to $V$. If $U = \{u\}$ (resp. $V = \{v\}$) then we simply write $u$ for $U$ (resp. $v$ for $V$) in these notations. The *distance* from $u$ to $v$, denoted by $dist(u, v)$, is the length of a shortest $(u, v)$-path, with the convention $dist(u, v) = +\infty$ if no such path exists.

A digraph is *connected* if its underlying graph is connected. It is *strongly connected* if for every ordered pair $(u, v)$ of its vertices, there exists a directed path from $u$ to $v$.

## 2 An improved bound on mader$\vec{\chi}(\overleftrightarrow{K_n})$

This section is devoted to the proof of Theorem 2. We need the two following Lemmas.

**Lemma 15** (Aboulker et al. [1, Lemma 31]). For every integer $k$ and every digraph $D$ with $\vec{\chi}(D) \ge 4k-3$, there is a subdigraph $H$ of $D$ with $\vec{\chi}(H) \ge k$ such that for every pair $u, v$ of distinct vertices in $H$, there is a directed path from $u$ to $v$ in $D$ whose internal vertices are in $V(D) \setminus V(H)$.

In particular, for every digraph $F$ and every arc $e$ in $F$,

$$ \mathrm{mader}_{\vec{\chi}}(F) \le 4 \cdot \mathrm{mader}_{\vec{\chi}}(F \setminus e) - 3. $$

We skip the proof of the following easy lemma.
**Lemma 16.** If $F_1 + F_2$ denotes the disjoint union of two digraphs $F_1$ and $F_2$, then $\mathrm{mader}_{\vec{\chi}}(F_1 + F_2) \le \mathrm{mader}_{\vec{\chi}}(F_1) + \mathrm{mader}_{\vec{\chi}}(F_2)$.

We are now ready to prove Theorem 2, let us first restate it.

**Proposition 2.** $\mathrm{mader}_{\vec{\chi}}(\overleftrightarrow{K}_n) \le 4^{\frac{2}{3}n^2+2n-\frac{8}{3}}$.

*Proof.* Let $f(n) = \mathrm{mader}_{\vec{\chi}}(\overleftrightarrow{K}_n)$ for every $n \ge 1$. Clearly $f(1) = 1$. Let $g(x) = 4^{\frac{2}{3}x^2+2x-\frac{8}{3}}$ for every positive real $x$. Observe that $g$ is non-decreasing. We will show by induction on $n$ that $f(n) \le g(n)$ for every positive integer $n$. For $n=1$, $f(1) = 1 = g(1)$. Now suppose $n \ge 2$.

If $n$ is even, by Lemmas 15 and 16 we deduce the following inequalities.

$$ 
\begin{aligned}
f(n) &\le 4^{\frac{n^2}{2}} \cdot \mathrm{mader}_{\vec{\chi}}(\overleftrightarrow{K}_{\frac{n}{2}} + \overleftrightarrow{K}_{\frac{n}{2}}) \\
&\le 4^{\frac{n^2}{2}} \cdot 2 \cdot f\left(\frac{n}{2}\right) \\
&\le 4^{\frac{n^2}{2}} \cdot 2 \cdot g\left(\frac{n}{2}\right) \\
&\le 4^{\frac{n^2}{2}+n} \cdot g\left(\frac{n}{2}\right).
\end{aligned}
$$

If $n$ is odd, then $f(n) \le 4^{2(n-1)}\mathrm{mader}_{\vec{\chi}}(\overleftrightarrow{K}_1 + \overleftrightarrow{K}_{n-1}) \le 4^{2(n-1)}(1 + f(n-1)) \le 4^{2n-1}f(n-1)$. Hence:

$$ 
\begin{aligned}
f(n) &\le 4^{2n-1}f(n-1) \\
&\le 4^{2n-1} \cdot 4^{\frac{(n-1)^2}{2}} \cdot \mathrm{mader}_{\vec{\chi}}(\overleftrightarrow{K}_{\frac{n-1}{2}} + \overleftrightarrow{K}_{\frac{n-1}{2}}) \\
&\le 4^{2n-1} \cdot 4^{\frac{(n-1)^2}{2}} \cdot 2 \cdot f\left(\frac{n-1}{2}\right) \\
&\le 4^{2n-1} \cdot 4^{\frac{(n-1)^2}{2}} \cdot 2 \cdot g\left(\frac{n-1}{2}\right) \\
&\le 4^{\frac{n^2}{2}+n-\frac{1}{2}} \cdot 2 \cdot g\left(\frac{n}{2}\right) \\
&= 4^{\frac{n^2}{2}+n} \cdot g\left(\frac{n}{2}\right).
\end{aligned}
$$

In both cases we have:

$$ f(n) \le 4^{\frac{n^2}{2}+n} \cdot g\left(\frac{n}{2}\right) = 4^{n^2(\frac{1}{2}+\frac{1}{6})+n(1+1)-\frac{8}{3}} = g(n). $$

□

# 3 Paths and cycles in large dicritical digraphs

This section is devoted to the proofs of Theorems 5 and 6. We first prove the following useful observation.

**Lemma 17.** For every integer $k$, if $D$ is a $k$-dicritical digraph and if $D'$ is obtained from $D$ by adding a vertex $u$ with $N^+(u) = N^-(u) = V(D)$, then $D'$ is $(k+1)$-dicritical.

*Proof.* First we show that $\chi(D') \ge k+1$. Indeed, if $\phi: V(D') \to [k]$ is a $k$-dicolouring of $D'$, then $\phi(v) \ne \phi(u)$ for every $v \in V(D)$, and so $\phi$ induces a $(k-1)$-dicolouring of $D$, a contradiction.

It remains to show that for every arc $vw$ in $D'$, $D' \setminus vw$ is $(k-1)$-dicolourable. If $vw \in A(D)$, then since $D$ is $k$-dicritical, $D \setminus vw$ admits a $(k-1)$-dicolouring $\phi: V(D) \to [k-1]$. Then extending $\phi$ to $V(D')$ by $\phi(u) = k$ yields a $k$-dicolouring of $D'$. If $u \in \{v, w\}$, then consider a $k$-dicolouring $\phi: V(D) \setminus \{v, w\} \to [k-1]$ of $D' - \{v, w\}$, which exists since $D' - \{v, w\}$ is a proper subdigraph of $D$. Now set $\phi(v) = \phi(w) = k$. Colour $k$ induces an acyclic digraph of $D' \setminus vw$, and this yields a $k$-dicolouring of $D' \setminus vw$. □
**Theorem 5.** For every integer $k \ge 3$, there are infinitely many $k$-dicritical digraphs without any directed path on $3k+1$ vertices.

*Proof.* Let $n$ be an odd integer. Let $D_{k,n}$ be the digraph constructed as follows. Start with the antidirected path $P = p_1 \dots p_n$ on $n$ vertices in which $d^+(p_1) = 1$. Add the digon $[p_1, p_n]$, and two vertices $x_1, x_2$ with a digon $[x_1, x_2]$. For every arc $uv$ of $P$, add the arcs $vx_i, x_iu$ for every $i \in [2]$. Finally, add $k-3$ vertices $x_3, \dots, x_{k-1}$ inducing a copy of $\overleftarrow{K}_{k-3}$ and add the digon $[x_{i+2}, u]$ for every $i \in [k-3]$ and every $u \in V(P) \cup \{x_1, x_2\}$. See Figure 2 for an illustration.

<figure><img src="image_2.png" /><figcaption>Figure 2: The digraph $D_{3,7}$. The antidirected path $P$ is in blue.</figcaption></figure>

Let us show that $D_{k,n}$ is $k$-dicritical. Since $D_{k,n}$ is obtained from $D_{3,n}$ by adding $k-3$ vertices linked to all other vertices by a digon, by Lemma 17 it is enough to show that $D_{3,n}$ is 3-dicritical.

First we show that $\vec{\chi}(D_{3,n}) > 2$. Suppose for contradiction that there is a 2-dicolouring $\phi: V(D_{3,n}) \rightarrow [2]$ of $D_{3,n}$. Without loss of generality, $\phi(x_1) = 1$ and $\phi(x_2) = 2$. For every arc $uv$ of $P$, for every $i \in [2]$, $uvx_iu$ is a directed triangle. This implies that $\phi(u) \neq \phi(v)$. Since $P$ has an odd number of vertices, $\phi(p_1) = \phi(p_n)$, which is a contradiction as $[p_1, p_n]$ is a digon in $D_{3,n}$.

Let $uv$ be an arc in $D_{3,n}$. We show that $\vec{\chi}(D_{3,n} \setminus uv) \le 2$. If $\{u, v\} = \{x_1, x_2\}$, set $\phi(x_1) = \phi(x_2) = \phi(p_1) = 1$, $\phi(p_2) = \dots = \phi(p_n) = 2$. If $\{u, v\} = \{p_1, p_n\}$, set $\phi(x_1) = 1$, $\phi(x_2) = 2$, $\phi(p_i) = 1$ if $i$ is even, $\phi(p_i) = 2$ if $i$ is odd. If $uv \in A(P)$, set $\phi(x_1) = 1$, $\phi(x_2) = 2$, and colour $V(P)$ such that the only monochromatic pair of adjacent vertices in $P$ is $\{u, v\}$. If $u \in V(P)$ and $v = x_i$, set $\phi(x_1) = 1$, $\phi(x_2) = 2$, $\phi(u) = i$, and colour $V(P-u)$ such that two adjacent vertices in $V(P-u)$ receive distinct colours. The other cases are symmetric. In each case, one can check that this gives a proper 2-dicolouring of $D_{3,n} \setminus uv$.

It remains to prove that $D_{k,n}$ does not contain a directed path on $3k+1$ vertices. Let $Q$ be a directed path in $D_{k,n}$. Let $y_1, \dots, y_\ell$ be the vertices of $V(Q) \cap \{x_1, \dots, x_{k-1}\}$ in order of appearance along $Q$. Let $Q_i$ be the subpath $Q|_{y_i, y_{i+1}}$ of $Q$ for every $i \in [\ell-1]$ and let $Q_0 = Q[\text{init}(Q), y_1[$ and $Q_\ell = Q|_{y_\ell}$, term$(Q)]$. Note that some $Q_i$s may be empty.

Then observe that at most one of the $Q_i$s intersects both $p_1$ and $p_n$. Except this one, which has at most three vertices, all the $Q_j$s have at most two vertices (because $P$ is anti-directed). We conclude that the number of vertices in $P$ is at most $3\ell + 3 \le 3k$. $\square$

**Theorem 6.** For every fixed integers $k \ge 2$ and $\ell \ge 3$, there are finitely many $k$-dicritical digraphs with no oriented cycle on at least $\ell$ vertices.

*Proof.* Let $k \ge 2$ be a fixed integer. We will show the existence of a function $f_k: \mathbb{N} \rightarrow \mathbb{N}$ such that every $k$-dicritical digraph on at least $f_k(\ell)$ vertices contains an oriented path on $\ell$ vertices. We will then use a result of Dirac to show that every $k$-dicritical digraph on at least $f_k(\frac{1}{4}\ell^2)$ vertices contains an oriented cycle on $\ell$ vertices, implying the result.

Given a digraph $H$, $cc(H)$ is the number of connected components of $H$ (i.e. the number of connected components of $UG(H)$). Our proof is strongly based on the following claim.
**Claim 6.1.** Let $D = (V, A)$ be a $k$-dicritical digraph and $S \subseteq V$, then $cc(D - S) \le (k - 1)^{|S|} \cdot 3^{\binom{|S|}{2}}$.

*Proof of claim.* Assume this is not the case, i.e. there exists a $k$-dicritical digraph $D$ and a subset of its vertices $S$ such that $cc(D - S) > (k - 1)^{|S|} \cdot 3^{\binom{|S|}{2}}$. We denote by $H_1, \dots, H_r$ the connected components of $D - S$.

For every $i \in [r]$, let $\alpha_i$ be a $(k-1)$-dicolouring of $D - V(H_i)$, the existence of which is guaranteed by the dicriticality of $D$. Let $s = |S|$ and $v_1, \dots, v_s$ be any fixed ordering of $S$. For every $i \in [r]$, we let $\sigma_i^1$ be the ordered set $(\alpha_i(v_1), \dots, \alpha_i(v_s))$. We also define $\sigma_i^2$ as the set of all ordered pairs $(u, v) \in S^2$ such that $D - V(H_i)$, coloured with $\alpha_i$, contains a monochromatic directed path from $u$ to $v$. We finally define the $i^{th}$ configuration $\sigma_i$ as the ordered pair $(\sigma_i^1, \sigma_i^2)$.

For every pair of vertices $u, v$ in $S$ and every $i \in [r]$, note that at most one of the ordered pairs $(u, v)$, $(v, u)$ actually belongs to $\sigma_i^2$, for otherwise $D - V(H_i)$, coloured with $\alpha_i$, contains a monochromatic directed cycle. Hence, the number of distinct configurations is at most $(k-1)^s \cdot 3^{\binom{s}{2}}$. By the pigeonhole principle, since $r > (k-1)^s \cdot 3^{\binom{s}{2}}$, there exist two distinct integers $i, j \in [r]$ such that $\sigma_i = \sigma_j$. Let $\alpha$ be the colouring of $D$ defined as follows:

$$ \alpha(v) = \begin{cases} \alpha_i(v) & \text{if } v \in (V(D) \setminus V(H_i)) \\ \alpha_j(v) & \text{otherwise.} \end{cases} $$

We claim that $\alpha$ is a $(k-1)$-dicolouring of $D$. Assume for a contradiction that it is not, so $D$, coloured with $\alpha$, contains a monochromatic directed cycle. Among all such cycles $C$, we choose one for which the size of $V(C) \cap V(H_i)$ is minimised. If $V(C) \cap V(H_i) = \emptyset$, then $C$ is a monochromatic directed cycle of $D - H_i$, a contradiction to the choice of $\alpha_i$. Analogously, we have $V(C) \setminus V(H_i) \neq \emptyset$ by choice of $\alpha_j$.

Assume first that $|V(C) \setminus V(H_i)| = 1$, implying that $C$ contains exactly one vertex $s$ in $S$ and $(V(C) \setminus \{s\}) \subseteq V(H_i)$. Since $\sigma_i^1 = \sigma_j^1$, we have $\alpha_i(s) = \alpha_j(s)$, which implies that $C$ is a monochromatic directed cycle of $D - H_j$ coloured with $\alpha_j$, a contradiction to the choice of $\alpha_j$.

Henceforth we can assume that $C$ contains a directed path $P$ on at least three vertices, with initial vertex $u$ and terminal vertex $v$, such that $V(P) \cap S = \{u, v\}$ and $V(P) \subseteq (V(H_i) \cup \{u, v\})$. The existence of $P$ ensures that $(u, v)$ belongs to $\sigma_j^2$. Hence, since $\sigma_i = \sigma_j$, there exists a monochromatic directed path $P'$ in $D - V(H_i)$ coloured with $\alpha_i$, from $u$ to $v$, and with the same color as $P$. Hence, replacing $P$ by $P'$ in $C$, we obtain a closed walk which, coloured with $\alpha$, contains a monochromatic directed cycle $C'$ such that $|V(C') \cap V(H_i)| < |V(C) \cap V(H_i)|$, a contradiction to the choice of $C$. $\diamond$

We are now ready to prove the existence of $f_k$. Let $D$ be a $k$-dicritical digraph whose underlying graph $G$ does not contain any path on $\ell$ vertices. Let $v$ be any vertex of $D$ and $T$ be a spanning DFS-tree of $G$ rooted in $v$ (recall that $D$ is connected since it is dicritical). Let $h$ be the depth of $T$ (i.e. the maximum number of vertices in a branch of $T$), then $h$ is at most $\ell$ since $G$ does not contain any path of length $\ell$.

For every vertex $x$, let $S_x$ be the ancestors of $x$ (including $x$ itself) in $T$ and $d_T(x)$ be the number of children of $x$ in $T$. Since $T$ is a DFS-tree, note that for every neighbour $y$ of $x$, $x$ and $y$ must belong to the same branch. Hence, $d_T(x) \le cc(D - S_x)$. Since $|S_x| \le h \le \ell$, we deduce from Claim 6.1 that $d_T(x) \le (k-1)^\ell \cdot 3^{\binom{\ell}{2}}$. Since $T$ is spanning, we obtain that $|V(D)| \le ((k-1)^\ell \cdot 3^{\binom{\ell}{2}})^{\ell-1} = f_k(\ell) - 1$.

Dirac proved that every 2-connected graph that contains a path of length $t$ actually contains a cycle of length at least $2\sqrt{t}$ (see [17]). It is straightforward to show that every $k$-dicritical digraph is 2-connected. Hence, if $D$ is a $k$-dicritical digraph on at least $f_k(\frac{1}{4}\ell^2)$ vertices, then $D$ contains an oriented cycle of length at least $\ell$, implying the result. $\square$

# 4 Subdivisions in digraphs with large digirth

This section is devoted to the proof of Theorem 8.

**Theorem 8.** Let $k \ge 1$ be an integer. For every non-empty digraph $F$, if $F^*$ is obtained from $F$ by subdividing every arc at most $k-1$ times, then $mader_{\chi}^{(k)}(F^*) \le \frac{1}{3}(4^{m(F)}+1)n(F) - 1)$.
*Proof.* We proceed by induction on $m(F)$, the result being trivial when $m(F) = 0$. Let $F$ be any digraph with $m > 0$ arcs, and let $F^*$ be a digraph obtained from $F$ by subdividing every arc at most $k-1$ times.

Let $uv \in A(F)$ be any arc, and $P = x_1, \dots, x_r$ its corresponding directed path in $F^*$ (where $u = x_1$ and $v = x_r$). Then we only have to prove that $\text{mader}_{\vec{\chi}}^{(k)}(F^* \setminus x_1x_2) \le \frac{4^{m(F)}n(F)-1}{3} + 1$. If this is true, then by Lemma 15, we get that $\text{mader}_{\vec{\chi}}^{(k)}(F^*) \le 4\left(\frac{4^{m(F)}n(F)-1}{3} + 1\right) - 3$ which shows the result.

Let $D$ be any digraph with dichromatic number at least $\frac{4^{m(F)}n(F)-1}{3} + 1$ and digirth at least $k$ and let $B \subseteq V(D)$ be a maximal acyclic set in $D$. Then $\vec{\chi}(D-B) \ge \frac{4^{m(F)}n(F)-1}{3}$, so by induction $D-B$ must contain a subdivision of $F \setminus uv$ where each arc has been subdivided at least $k-1$ times. This is also a subdivision of $F^* - \{x_2, \dots, x_{r-1}\}$. Let $y$ be the vertex in $D-B$ corresponding to $x_r$. By maximality of $B$, there must be a directed cycle $C$ in $D$ such that $V(C) \cap V(D-B) = \{y\}$. Note that $C$ has length at least $k$. Thus, ignoring the leaving arc of $y$ in $C$, we have found a subdivision of $F^* \setminus x_1x_2$ in $D$, showing the result. $\square$

# 5 Subdivisions of trees in digraphs with large digirth

This section is devoted to the proofs of Theorems 9 and 10.

**Theorem 9.** Let $k \ge 1$ be an integer and let $T$ be a bidirected tree. If $T^*$ is obtained from $T$ by subdividing every arc at most $k-1$ times, then $\text{mader}_{\vec{\chi}}^{(2k)}(T^*) \le \text{mader}_{\vec{\chi}}(T) = n(T)$.

*Proof.* We proceed by induction on $n(T)$. Suppose $n(T) \ge 2$, the result being trivial when $n(T) = 1$.

Let $f$ be a leaf of $T$ with neighbour $p$, and we denote by $(T-f)^*$ the bidirected tree $T-f$ with every arc subdivided exactly $k-1$ times. By induction hypothesis $\text{mader}_{\vec{\chi}}^{(2k)}((T-f)^*) \le \text{mader}_{\vec{\chi}}(T-f) = n(T)-1$. Let $D$ be a digraph with $\text{digirth}(D) \ge 2k$ and $\vec{\chi}(D) \ge n(T)$, and consider a maximal acyclic set $A$ in $D$. Then $\vec{\chi}(D-A) \ge n(T)-1$ and so by induction hypothesis, $D-A$ contains a subdivision of $(T-f)^*$. Let $y \in V(D)$ be the vertex corresponding to $p \in V(T)$ in the subdivision of $(T-f)^*$ contained in $D$. By maximality of $A$, $A+y$ contains a directed cycle $C$ with $V(C) \setminus A = \{y\}$. As $\text{digirth}(D) \ge 2k$, $C$ has length at least $2k$. Then the subdivision of $(T-f)^*$ in $D-A$ together with $C$ gives the desired subdivision of $T^*$. $\square$

**Theorem 10.** Let $k \ge 1$ be an integer. Let $D$ be a digraph, $T$ be an oriented tree and $T^*$ obtained from $T$ by subdividing every arc at most $k-1$ times. If $\vec{\chi}(D) \ge \text{mader}_{\vec{\chi}}(T)$ and $\text{digirth}(D) \ge k$, then $D$ contains $T^*$ as a subdigraph.

*Proof.* We proceed by induction on $n(T)$. Suppose $n(T) \ge 2$, the result being trivial when $n(T) = 1$.

For every arc $e$ of $T$, we denote by $s(e)$ the number of subdivisions of $e$ in $T^*$. Let $f$ be a leaf of $T$ with neighbour $p$, and we denote by $(T-f)^*$ the oriented tree $T-f$ where every arc $e$ is subdivided $s(e) \le k-1$ times.

Let $D$ be a digraph with $\text{digirth}(D) \ge k$ and $\vec{\chi}(D) \ge n(T)$, and consider a maximal acyclic set $A$ in $D$. We have $\vec{\chi}(D-A) \ge n(T)-1$ and, by the induction hypothesis, $D-A$ contains a copy of $(T-f)^*$. Let $y \in V(D) \setminus A$ be the vertex corresponding to $p \in V(T)$ in the copy of $(T-f)^*$ contained in $D$. By maximality of $A$, $A+y$ contains a directed cycle $C$ with $C \setminus A = \{y\}$. As $\text{digirth}(D) \ge k$, $C$ has length at least $k$.

If the arc between $p$ and $f$ goes from $p$ to $f$ then we define $P$ as the directed path on $s(pf)$ vertices starting from $y$ along $C$. Otherwise, it goes from $f$ to $p$ and then we define $P$ as the directed path on $s(fp)$ vertices, along $C$, ending on $y$. In both cases, the copy of $(T-f)^*$ in $D-A$ together with $P$ gives the desired copy of $T^*$. $\square$

# 6 Subdivisions in digraphs of large out-degree and large digirth

## 6.1 Subdivisions of $C(k, k)$

This section is devoted to the proof of Theorem 11.
**Theorem 11.** For every integer $k \ge 2$, every digraph $D$ with $\delta^+(D) \ge 2$ and digirth($D$) $\ge 8k-6$ contains a subdivision of $C(k, k)$.

*Proof.* We will prove the following stronger statement: for every digraph $D$ with digirth($D$) $\ge 8k-6$ and $v_0 \in V(D)$, if $d^+(v_0) \ge 1$ and $d^+(v) \ge 2$ for every $v \in V(D) \setminus \{v_0\}$, then $D$ contains a subdivision of $C(k, k)$. We now consider a counterexample to this statement with minimum number of vertices, and minimum number of arcs if equality holds.

**Claim 11.1.** $D$ is strongly connected.

*Proof of claim.* Let $C$ be a terminal strongly connected component of $D$, that is a strongly connected component such that there is no arc going out of $C$. Then $C$ is also a counterexample, so by minimality of $D$ we have $D = C$, and $D$ is strongly connected. $\diamond$

**Claim 11.2.** $d^+(v) = 2$ for every vertex $v \ne v_0$ and $d^+(v_0) = 1$.

*Proof of claim.* If $v \ne v_0$ is a vertex with at least 3 out-neighbours $w_1, w_2, w_3$, then $D \setminus vw_3$ is a smaller counterexample. Similarly, if $d^+(v_0) > 1$, then $v_0$ has at least two distinct out-neighbours $w_1, w_2$, and $D \setminus vw_2$ is a smaller counterexample. $\diamond$

Given two vertices $u, v$ of $D$, a $(u, v)$-vertex-cut is a vertex $x \in V(D) \setminus \{u, v\}$ which intersects every $(u, v)$-path of $D$.

**Claim 11.3.** Let $u, v$ be two vertices in $D$. If $\text{dist}(u, v) \le 7k-6$, then there exists a $(v, u)$-vertex-cut.

*Proof of claim.* Suppose the contrary for contradiction. Then by Menger's theorem, there exist two internally vertex-disjoint $(v, u)$-paths $P_1$ and $P_2$. As $\text{digirth}(D) \ge 8k-6$, both $P_1$ and $P_2$ have length at least $k$, and so $P_1 \cup P_2$ is a subdivision of $C(k, k)$ with source $v$ and sink $u$. $\diamond$

For every directed cycle $C$ in $D$, let $\rho(C)$ be the number of vertices in the largest connected component of $D - V(C)$. We say that $C$ is isometric if for every $u, v \in V(C)$, $C$ contains a shortest $(u, v)$-path in $D$. Clearly $D$ contains an isometric cycle (it is enough to take a minimum directed cycle), and we consider among them an isometric cycle $C$ which maximises $\rho(C)$.

Let $ab$ be an arc along $C$. Let $c_1, \dots, c_\ell$ be the $(b, a)$-vertex-cuts in $D$. Observe that at least one such vertex-cut exists by Claim 11.3. As $C$ contains a $(b, a)$-path, all these vertices belong to $V(C)$, and we suppose that they appear in this order $c_1, \dots, c_\ell$ along $C$ starting at $b$. By convention we also define $c_0 = b$ and $c_{\ell+1} = a$.

**Claim 11.4.** $\text{dist}(c_i, c_{i+1}) \le k-1$ for every $i = 0, \dots, \ell$.

*Proof of claim.* Suppose for contradiction that $\text{dist}(c_i, c_{i+1}) \ge k$. Assume first that there exists a $(c_i, c_{i+1})$-vertex-cut $x$. We claim that $x$ is also a $(b, a)$-vertex-cut. Consider a $(b, a)$-path $Q$. Then $Q$ passes through $c_i$ and $c_{i+1}$ in this order, otherwise the concatenation of $Q[b, c_{i+1}]$ and $C[c_{i+1}, a]$ is a $(b, a)$-path avoiding $c_i$, a contradiction. By definition of $x$, it belongs to $Q[c_i, c_{i+1}]$. Hence $x$ intersects every $(b, a)$-path, and so $x \in \{c_1, \dots, c_\ell\}$, a contradiction since $c_1, \dots, c_\ell$ are in this order along $C$.

This shows, by Menger's theorem, that there are two internally vertex-disjoint $(c_i, c_{i+1})$-paths $P_1, P_2$. Then $P_1$ and $P_2$ have length at least $k$, and so $P_1 \cup P_2$ is a subdivision of $C(k, k)$ with source $c_i$ and sink $c_{i+1}$, a contradiction. $\diamond$

Let $i_0$ be the least index $i$ such that $\text{dist}(b, c_i) \ge k$, and let $i_1$ be the largest index $i$ such that $\text{dist}(c_i, a) \ge k$. By choice of $i_0$, we have $\text{dist}(b, c_{i_0-1}) \le k-1$. By Claim 11.4, we have $\text{dist}(c_{i_0-1}, c_{i_0}) \le k-1$, which implies $\text{dist}(b, c_{i_0}) \le \text{dist}(b, c_{i_0-1}) + \text{dist}(c_{i_0-1}, c_{i_0}) \le 2k-2$. Similarly we have $\text{dist}(c_{i_1}, a) \le 2k-2$. Therefore, we have

$$ \text{dist}(c_{i_0}, c_{i_1}) = |V(C)| - \text{dist}(c_{i_1}, a) - 1 - \text{dist}(b, c_{i_0}) \ge 4k-3, $$

which implies $i_1 - i_0 \ge 5$ by Claim 11.4. See Figure 3 for an illustration.

We now define $d_i = c_{i+i_0}$ for $i = 0, \dots, 5$ and we consider these indices modulo 6. For every $i = 0, \dots, 5$, let $X_i$ be the set of vertices reachable from $d_i$ in $D - d_{i+1}$.
<figure><img src="image_3.png" /><figcaption>Figure 3: The structure of C in D. The solid and dashed arcs represent the arcs of C. A dotted arc from u to v illustrates the existence of two internally-disjoint directed path from u to v in D.</figcaption></figure>

**Claim 11.5.** For every $i = 0, \dots, 5$, $X_i \cap C = C[d_i, d_{i+1}]$.

*Proof of claim.* We first consider the case $i \in \{0, \dots, 4\}$. Assume for a contradiction that there exists a directed path $P$ from $V(C[d_i, d_{i+1}])$ to $V(C) \setminus V(C[d_i, d_{i+1}])$ with internal vertices disjoint from $C$. Let $u$ be init($P$) and $v$ be term($P$). If $v \in V(C[d_{i+1}, a])$, then $C[b, u] \cup P \cup C[v, a]$ is a $(b, a)$-path disjoint which avoids $d_{i+1}$, a contradiction. Otherwise $v \in C[b, d_i]$, and then $P$ has length at least $k$ because, since $C$ is isometric,

$$ \mathrm{dist}_P(u, v) \ge \mathrm{dist}_C(u, v) \ge \mathrm{dist}_C(d_5, b) \ge \mathrm{dist}_C(c_{i_1}, a) \ge k. $$

But then $P \cup C[u, v]$ is a subdivision of $C(k, k)$ with source $u$ and sink $v$, a contradiction to $D$ being a counterexample.

Now suppose $i = 5$. Consider first a directed path $P$ from $u \in C[d_5, a]$ to $v \in C]d_0, d_5[$ internally disjoint from $C$. Then $P$ has length at least $k$ because

$$ \mathrm{dist}_P(u, v) \ge \mathrm{dist}_C(u, v) \ge \mathrm{dist}_C(b, d_0) \ge k. $$

Thus $P \cup C[u, v]$ is a subdivision of $C(k, k)$ with source $u$ and sink $v$, a contradiction. Consider finally a directed path $P$ from $u \in C[b, d_0[$ to $v \in C]d_0, d_5[$. Then $d_0$ is not a $(b, a)$-cut in $D$, a contradiction. $\diamond$

**Claim 11.6.** For every distinct $i, j \in \{0, \dots, 5\}$, we have

$$ (i) \quad X_i \cap X_j = \emptyset \text{ if } i \notin \{j-1, j+1\}, \text{ and} $$

$$ (ii) \quad X_i \cap X_{i+1} = \emptyset \text{ if } v_0 \notin X_i \cup X_{i+1}. $$

*Proof of claim.* We first prove (i). Let us fix two distinct integers $i, j \in \{0, \dots, 5\}$ such that $i \notin \{j-1, j+1\}$. Assume for a contradiction that $X_i \cap X_j \ne \emptyset$. Note that $X_i \cap X_j \ne V(D)$ because $d_{i+1} \notin X_i$. Therefore, since $D$ is strongly connected by Claim 12.2, there is an arc $uv$ such that $u \in X_i \cap X_j$ and $v \in V(D) \setminus (X_i \cap X_j)$. Assume first that $v \in X_j \setminus X_i$. Since $v \notin X_i$, we must have $v = d_{i+1}$. Hence $d_{i+1} \in X_j$, a contradiction to Claim 11.5. Symmetrically, if $v \in X_i \setminus X_j$ then $v = d_{j+1}$ by definition of $X_j$, implying that $d_{j+1} \in X_i$, a contradiction to Claim 11.5. Finally if $v \notin (X_i \cup X_j)$, by definition of $X_i$ and $X_j$, we must have $v = d_{i+1} = d_{j+1}$, a contradiction. This proves (i).

We now prove (ii). Assume for a contradiction that $v_0 \notin X_i \cup X_{i+1}$ and $X_i \cap X_{i+1} \ne \emptyset$. Recall that $X_i \cap X_{i+1} \ne V(D)$ because $d_{i+1} \notin X_i$. Therefore, since $D$ is strongly connected, there is an arc $uv$ such that $u \in X_i \cap X_{i+1}$ and $v \in V(D) \setminus (X_i \cap X_{i+1})$. First, if $v \in V(D) \setminus (X_i \cup X_{i+1})$ then, by definition of $X_i$,
v must be $d_{i+1}$, and by definition of $X_{i+1}$, v must be $d_{i+2}$, a contradiction. Next if $v \in X_i \setminus X_{i+1}$, then by definition of $X_{i+1}$, v must be $d_{i+2}$, but $d_{i+2} \notin X_i$ by Claim 11.5, a contradiction. Then we may assume that $v \in X_{i+1} \setminus X_i$, and by definition of $X_i$, v must be $d_{i+1}$. As $u \in X_{i+1}$, there is a directed path P from $V(C[d_{i+1}, d_{i+2}])$ to u in $D - d_{i+2}$ internally disjoint from C. Let x be init(P). If $x \neq d_{i+1}$, then the union of P $\cup$ ud$_{i+1}$ (which has length at least k because digirth(D) $\geq$ 8k-6 $\geq$ 2k and dist(d$_{i+1}$, x) $\leq$ k by Claim 11.4) and C[x, d$_{i+1}$] (which has length at least k because $|V(C)|$ $\geq$ 8k-6 $\geq$ 2k and dist(d$_{i+1}$, x) $\leq$ k by Claim 11.4) is a subdivision of C(k, k) with source x and sink d$_{i+1}$, a contradiction.

So we assume that $x = d_{i+1}$, that is $P \cup ud_{i+1}$ is a cycle $C'$ with $V(C') \cap V(C) = \{d_{i+1}\}$, and $u \in V(C') \cap X_i \cap X_{i+1}$. Let w be the vertex in $V(C') \cap X_i$ such that $\text{dist}_{C'}(w, d_{i+1})$ is maximum (the existence of w is guaranteed because $u \in V(C') \cap X_i$), and let Q be a $(d_i, w)$-path in $D[X_i]$. If $\text{dist}_{C'}(w, d_{i+1}) \le k-1$, then $C'[d_{i+1}, w]$ has length at least k, and $C[d_{i+1}, d_i] \cup Q$ has length at least k. Moreover, the directed paths $C'[d_{i+1}, w]$ and $C[d_{i+1}, d_i] \cup Q$ are internally vertex-disjoint by the choice of P, w and Q. Hence their union is a subdivision of C(k, k) with source $d_{i+1}$ and sink w, a contradiction. Henceforth we suppose that $\text{dist}_{C'}(w, d_{i+1}) \ge k$.

We now prove the following statement.

$$D - d_{i+1} \text{ does not contain any directed path R from } V(C') \text{ to } V(C). \quad (1)$$

Assume for a contradiction that such a directed path R exists. We assume that R is internally disjoint from $V(C') \cup V(C)$, for otherwise we can extract a subpath of R with this extra property. Let $y = \text{init}(R)$ and $z = \text{term}(R)$. Then by Claim 11.5, $z$ belongs to $V(C][d_{i+1}, d_{i+2}])$. Observe that $y \in V(C']d_{i+1}, w[)$, for otherwise $y$ belongs to $X_i$ and so does $z$, a contradiction to Claim 11.5. But then the union of $R \cup C[z, d_{i+1}]$ and $C'[c, d_{i+1}]$ is a subdivision of $C(k, k)$ with source $y$ and sink $d_{i+1}$, a contradiction to D being a counterexample. This shows (1).

Let U be the set of vertices reachable from $d_i$ in $D \setminus d_{i+1}t$ where $t$ is the successor of $d_{i+1}$ in C. We claim that $U \subseteq X_i \cup X_{i+1}$. Let u be any vertex in U. By definition, there is a directed path $R'$ from $d_i$ to u in $D \setminus d_{i+1}t$. If $d_{i+1} \notin V(R')$, then $u \in X_i$. Else if $d_{i+1} \in V(R')$ and $d_{i+2} \notin V(R')$, then $u \in X_{i+1}$. Henceforth assume that both $d_{i+1}$ and $d_{i+2}$ belong to $R'$. Observe that $d_{i+1}$ is before $d_{i+2}$ along $R'$, otherwise $d_{i+2} \in X_i$, a contradiction to Claim 11.5. Since $d_D^+(d_{i+1}) = 2$, the successor of $d_{i+1}$ in $R'$ is also its successor in $C'$. Hence $R'[d_{i+1}, d_{i+2}]$ contains a subpath R from $V(C') \setminus \{d_{i+1}\}$ to $V(C) \setminus \{d_{i+1}\}$ internally disjoint from $V(C') \cup V(C)$, a contradiction to (1).

This proves that $U \subseteq X_i \cup X_{i+1}$ and in particular, $v_0 \notin U$. Set $v'_0 = d_{i+1}$, $D' = D[U]$. Then $D'$ equipped with $v'_0$ is such that every vertex in U has out-degree 2 in $D'$ except $v'_0$ which has out-degree at least 1. By minimality of $|V(D)|$, $D'$ contains a subdivision of $C(k, k)$ and so does D, a contradiction. ◇

By (i) of the previous claim, there is an index $j \in \{0, \dots, 5\}$ such that $v_0 \notin X_{j-1}$. Since D is strongly connected, $\cup_{i=0}^5 X_i = V(D)$, and so there is an index $i \in \{0, \dots, 5\}$ such that $v_0 \in (X_i \setminus X_{i-1})$. From now on, we fix such an index $i \in \{0, \dots, 5\}$, and we set

$$\begin{align*}
Y_0 &= X_{i-1} \cup X_i \cup X_{i+1} \cup X_{i+2}, \\
Y_1 &= X_{i+3}, \text{ and} \\
Y_2 &= X_{i+4}.
\end{align*}$$

Note that $v_0 \notin X_{i-1} \cup X_{i+2}$, and so, by Claim 11.6, $Y_0, Y_1, Y_2$ are pairwise vertex-disjoint. Moreover, $Y_0 \setminus V(C), Y_1 \setminus V(C), Y_2 \setminus V(C)$ are pairwise non adjacent by definition of the $X_j$s (i.e. there is no arc of D with head and tail in different parts of $(Y_0 \setminus V(C), Y_1 \setminus V(C), Y_2 \setminus V(C))$). Consider a connected component A of $D - V(C)$ of maximal size, that is with $|A| = \rho(C)$. Then A is included in one of $Y_0, Y_1, Y_2$. Let $j \in \{1, 2\}$ be such that $A \cap Y_j = \emptyset$. Let q be the predecessor of $d_{i+j+3}$ in C. Let S be the set of vertices reachable from q in $D - d_{i+j+3}$. Observe that S is a subset of $X_{i+j+2}$. We claim that $D[S]$ is not acyclic. Indeed, for every vertex u $\in$ S, $N_D^+(u) \subseteq N_{D[S]}^+(u) \cup \{d_{i+j+3}\}$. Since $v_0 \notin S$, for every vertex u $\in$ S, $d_{D[S]}^+(u) \ge d_D^+(u) - 1 = 1$. Therefore $D[S]$ has minimum out-degree at least 1. Let $C'$ be an isometric cycle in $D[S]$.

Let us show that $C'$ is an isometric cycle in D. Suppose on the contrary that there is a directed path P from $x \in V(C')$ to $y \in V(C')$ internally disjoint from $V(C')$ of length smaller than $\text{dist}_{C'}(x, y)$. As P is not included in S, P must contain $d_{i+j+3}$. Let $d_k$ be the last vertex along P in $\{d_j | j = 0, \dots, 5\}$. We
have $y \in X_k$ by definition of $k$ and $y \in X_{i+j+2}$ because $y \in S \subseteq X_{i+j+2}$. Therefore $y \in X_k \cap X_{i+j+2}$. Since $v_0 \notin X_{i+j+1} \cup X_{i+j+2} \cup X_{i+j+3}$, by Claim 11.6, we deduce that $k = i + j + 2$. Hence $P$ contains a directed path from $d_{i+j+3}$ to $d_{i+j+2}$. This implies:

$$
\begin{align*}
dist_{C'}(x, y) &\ge \text{length}(P) && \text{by definition of } P \\
&\ge \text{dist}_D(d_{i+j+3}, d_{i+j+2}) && \text{because } P \text{ contains } d_{i+j+3} \text{ and } d_{i+j+2} \\
&= \text{dist}_C(d_{i+j+3}, d_{i+j+2}) && \text{because } C \text{ is isometric} \\
&= |V(C)| - \text{dist}_C(d_{i+j+2}, d_{i+j+3}) \\
&\ge (8k-6) - (k-1) \ge k && \text{by Claim 11.4.}
\end{align*}
$$

Therefore both $P$ and $C'[x, y]$ have length at least $k$, implying that $P \cup C'[x, y]$ is a subdivision of $C(k, k)$ with source $x$ and sink $y$, a contradiction to $D$ being a counterexample. This proves that $C'$ is isometric in $D$.

By definition, $N(A) \subseteq V(C) \cup A$. Since $D$ is strongly connected, $A$ has an in-neighbour in $V(C)$. Since $A \cap Y_j = \emptyset$ by choice of $j$, $A$ has an in-neighbour in $C[d_{i+j+3}, d_{i+j+2}]$. Hence, the connected component in $D - V(C')$ which contains $A$ is strictly larger than $A$, which contradicts the maximality of $\rho(C)$, and concludes the proof of the theorem. $\square$

## 6.2 Subdivisions of $C(2, 2)$ in oriented graphs

This section is devoted to the proof of Theorem 12.

**Theorem 12.** Every oriented graph $D$ with $\delta^+(D) \ge 2$ contains a subdivision of $C(2, 2)$.

*Proof.* Suppose for contradiction that there exists an oriented graph $D$ with $\delta^+(D) \ge 2$ that contains no subdivision of $C(2, 2)$. Assume that $|V(D)|$ is minimum, and that among such minimum counterexamples, $|A(D)|$ is minimum.

**Claim 12.1.** For every vertex $v \in V(D)$, $d^+(v) = 2$.

*Proof of claim.* If $v$ is a vertex with least 3 out-neighbours $w_1, w_2, w_3$, then $D \setminus vw_3$ is a smaller counterexample. $\diamond$

**Claim 12.2.** $D$ is strongly connected. In particular, $d^-(v) \ge 1$ for every vertex $v$.

*Proof of claim.* Let $C$ be a terminal strongly connected component of $D$. Then $C$ is also a counterexample, so by minimality of $D$ we have $D = C$, and $D$ is strongly connected. $\diamond$

**Claim 12.3.** For every vertex $v \in V(D)$, $d^-(v) \ge 2$.

*Proof of claim.* Suppose that $v$ is a vertex which has at most one in-neighbour. By Claim 12.2, it must have a unique in-neighbour $u$, and let $w_1, w_2$ be its two out-neighbours. If $w_1$ is non adjacent to $u$, then consider $D' = D - v \cup uw_1$. By minimality of $D$, $D'$ contains a subdivision $F$ of $C(2, 2)$, and as $F \not\subseteq D$, we have $uw_1 \in A(F)$. But then $F \setminus uw_1 \cup uv \cup vw_1 \subseteq D$ is a subdivision of $C(2, 2)$. Hence there is an arc between $u$ and $w_1$. Similarly, there is an arc between $u$ and $w_2$.

If $w_1u, w_2u \in A(D)$, then the union of the directed paths $vw_1u$ and $vw_2u$ yields a copy of $C(2, 2)$ in $D$. Moreover, if $uw_1, uw_2 \in A(D)$, then $d^+(u) \ge 3$, a contradiction to Claim 12.1. Hence, without loss of generality, $w_1u, uw_2 \in A(D)$.

As $D$ is strongly connected, there is a directed path $P$ from $w_2$ to $\{u, v, w_1\}$ with internal vertices disjoint from $\{u, v, w_1, w_2\}$. The terminal vertex of $P$ is not $v$, as the only in-neighbour of $v$ is $u$. So the terminal vertex of $P$ is either $u$ or $w_1$. If it is $w_1$, then the union of the directed paths $uvw_1$ and $uP$ yields a subdivision of $C(2, 2)$. If $u$ is the end-vertex of $P$, then the union of the directed paths $vw_1u$ and
vP yields a subdivision of $C(2, 2)$. In both cases, we find a subdivision of $C(2, 2)$ in $D$, a contradiction.
$\diamond$

**Claim 12.4.** *D* is 2-diregular.

*Proof of claim.* By Claim 12.1, we know that, for each $v \in V(D)$, $d^+(v) = 2$. It implies that $|A(D)| = \sum_{v \in V(D)} d^+(v) = 2|V(D)|$. Since $|A(D)|$ is also equal to $\sum_{v \in V(D)} d^-(v)$, we get by Claim 12.3 that for every vertex $v$ of $D$, $d^-(v) = d^+(v) = 2$, which implies that $D$ is 2-diregular. $\diamond$

**Claim 12.5.** For every arc $vw$, $w$ has a neighbour in $N^-(v)$.

*Proof of claim.* Let $u_1, u_2$ be the in-neighbours of $v$. If $w$ has no neighbour in $\{u_1, u_2\}$, consider $D' = D - v \cup u_1w \cup u_2w$. By minimality of $D$, there exists a subdivision $F$ of $C(2, 2)$ in $D'$. If neither $u_1w$ nor $u_2w$ belongs to $A(F)$, then $F \subseteq D$, a contradiction. If both $u_1w$ and $u_2w$ belong to $A(F)$, then $w$ is the sink of $F$ and $F \setminus w_1 \cup v$ is a subdivision of $C(2, 2)$ in $D$, a contradiction. If exactly one of $u_1w$ and $u_2w$ belongs to $A(F)$, say $u_1w$, then $F \setminus u_1w \cup \{u_1v, vw\}$ is a subdivision of $C(2, 2)$ in $D$, a contradiction. Hence $w_1$ has a neighbour in $\{u_1, u_2\}$. $\diamond$

**Claim 12.6.** For every vertex $v$ with in-neighbourhood $u_1, u_2$ and out-neighbourhood $w_1, w_2$, either $\{w_1u_1, w_2u_2\} \subseteq A(D)$ or $\{w_1u_2, w_2u_1\} \subseteq A(D)$. In particular, every vertex belongs to two different directed triangles.

*Proof of claim.* By Claim 12.5, $w_1$ has a neighbour in $\{u_1, u_2\}$. Without loss of generality, suppose that it is $u_1$. We now show that $w_1u_1 \in A(D)$, so assume for a contradiction that $u_1w_1 \in A(D)$. By Claim 12.5 $u_1$ has an in-neighbour $x$ which is also a neighbour of $w_1$.

If $x = u_2$, then $\{u_1, u_2, v, w_1\}$ contains a copy of $C(2, 2)$ with source $u_2$ and sink $w_1$. If $x = w_2$, then either $w_2w_1 \in A(D)$ and $w_1$ has in-degree 3, a contradiction to Claim 12.4, or $w_1w_2 \in A(D)$ and $\{u_1, v, w_1, w_2\}$ contains a copy of $C(2, 2)$ with source $u_1$ and sink $w_2$. Hence $x, u_1, u_2, v, w_1, w_2$ are distinct.

Moreover, $xw_1 \notin A(D)$ for otherwise $w_1$ has in-degree 3 contradicting Claim 12.4. Hence $w_1x \in A(D)$. Consider the out-neighbour $y$ of $w_1$ distinct from $x$. By Claim 12.5, $y$ has a neighbour in $N^-(w_1) = \{u_1, v\}$. If $v$ is a neighbour of $y$, then $y \in \{u_2, w_2\}$. If $y = w_2$, then $\{u_1, v, w_1, w_2\}$ contains a copy of $C(2, 2)$ with source $u_1$ and sink $w_2$. If $y = u_2$, then the union of the directed paths $w_1u_2v$ and $w_1xu_1v$ yields a subdivision of $C(2, 2)$ with source $w_1$ and sink $v$.

Hence $y$ is not a neighbour of $v$, and so $y$ is a neighbour of $u_1$. If $u_1y \in A(D)$, then $u_1$ has out-degree at least 3, contradicting Claim 12.1. If $yu_1 \in A(D)$, then $\{w_1, x, u_1, y\}$ contains a copy of $C(2, 2)$ with source $w_1$ and sink $u_1$. In both cases, we reach a contradiction.

This proves that $w_1u_1 \in A$. Similarly, $w_2$ has an out-neighbour in $N^-(v) = \{u_1, u_2\}$. If $w_2u_1 \in A(D)$, then $\{v, w_1, w_2, u_1\}$ contains a copy of $C(2, 2)$ with source $v$ and sink $u_1$, a contradiction. Hence $w_2u_1 \notin A(D)$, and so $w_2u_2 \in A(D)$ as claimed. $\diamond$

**Claim 12.7.** Let $t_1$ and $t_2$ be two different directed triangles of $D$. Then $|V(t_1) \cap V(t_2)| \le 1$.

*Proof of claim.* Since $D$ is an oriented graph, then it is clear that $|V(t_1) \cap V(t_2)| \le 2$. Assume now that $V(t_1) = \{x, y, z\}$ and $V(t_2) = \{x, y, w\}$, where $z \ne w$. Assume without loss of generality that $xy \in A(t_1)$, then $xy \in A(t_2)$ because $x$ and $y$ must be adjacent in $t_2$, and $D$ does not contain any digon. Now $t_1 \cup t_2$ contains a copy of $C(2, 2)$ with source $y$ and sink $x$, a contradiction. $\diamond$

Consider the undirected graph $H$ whose vertices are the directed triangles in $D$, and such that two triangles $t$ and $t'$ are adjacent if and only if they share a common vertex.

By Claim 12.7 and Claim 12.4, $H$ is a subcubic graph. Moreover, by Claim 12.6, $H$ must be a cubic graph. In particular $H$ is not a forest and so it contains an induced cycle $C = (t_1, \dots, t_k, t_1)$. Let $t_1 = (x, y, z, x)$ and suppose (by possibly relabelling $t_1$ and $C$) that $V(t_1) \cap V(t_k) = \{x\}$ and $V(t_1) \cap V(t_2) = \{y\}$. Let $P$ be a directed path in $D$ with vertices in $V(t_2) \cup \dots \cup V(t_k)$ from $y$ to $x$. Observe that $z \notin V(P)$ because $C$ is an induced cycle of $H$. Then $P \cup (y, z, x)$ is a subdivision of $C(2, 2)$ in $D$, a contradiction. This proves the theorem. $\square$
## 6.3 Subdivisions of out-stars

This section is devoted to the proofs of Theorems 13 and 14.

**Theorem 13.** For every positive integers $k, \ell$, every digraph with $\delta^+(D) \ge k$ and $\text{digirth}(D) \ge \frac{k^\ell-1}{k-1}+1$ contains a copy of $S_k^{+(\ell)}$ with centre $u$ for every chosen vertex $u$.

*Proof.* Let $D$ be such a digraph. By taking $|A(D)|$ minimal, we can suppose that $d^+(v) = k$ for every vertex $v \in V(D)$. Let $W$ be the set of vertices at distance at least $\ell$ from $u$. If there are $k$ vertex-disjoint $(u, W)$-paths then these directed paths have length at least $\ell$ and so they form a copy of $S_k^{+(\ell)}$. Otherwise, by Menger's Theorem, there is a set $S \subseteq V(D) \setminus \{u\}$ of $k-1$ vertices such that there is no $(u, W)$-path in $D-S$. Let $R$ be the set of vertices reachable from $u$ in $D-S$. Then every vertex in $R$ is at distance at most $\ell-1$ from $u$, so $|R| \le \frac{k^\ell-1}{k-1}$. As $D$ has digirth at least $\frac{k^\ell-1}{k-1}+1$, this implies that $D[R]$ is acyclic. Let $r \in R$ be a sink in $D[R]$. Then all the out-neighbours of $r$ in $D$ are in $S$, and so $d^+(r) \le k-1$, a contradiction. $\square$

**Theorem 14.** Let $D$ be a digraph with $\delta^+(D) \ge 2$. If $\text{digirth}(D) \ge 2\ell$, then $D$ contains a copy of $S_2^{+(\ell)}$.

*Proof.* Suppose for contradiction that there is such a digraph $D$ containing no copy of $S_2^{+(\ell)}$. We assume $\ell \ge 2$, the result being trivial when $\ell = 1$. Without loss of generality, we may also assume that $d^+(v) = 2$ for every vertex $v$ in $D$. By considering only one terminal strongly connected component of $D$, we can also assume that $D$ is strong. Let $u$ be a vertex in $D$, and let $w$ be a vertex at distance exactly $\ell$ from $u$. Such a vertex exists because, as $D$ is strong, $u$ has an in-neighbour, which is at distance at least $2\ell-1 \ge \ell+1$ from $u$.

Let us fix $P$ a shortest directed path from $u$ to $w$. A $P$-tricot is a sequence of pairwise vertex-disjoint directed paths $Q_1, \dots, Q_r$ (where $r$ is the size of the tricot) such that for every $i \in [r]$:

* $V(Q_i) \cap V(P) = \{\text{term}(Q_i), \text{init}(Q_i)\}$,

* $\text{init}(Q_1) = u$,

* $\text{init}(Q_{i+1}) = \text{pred}_P(\text{term}(Q_i))$ if $i < r$,

* there is an arc from $\text{pred}_{Q_i}(\text{term}(Q_i))$ to $V(P)\text{init}(Q_i), \text{term}(Q_i)]$.

<figure><img src="image_4.png" /><figcaption>Figure 4: An example of a $P$-tricot of size 3. Dotted arcs represent directed paths.</figcaption></figure>

Let us first prove that $D$ admits a $P$-tricot. Let $Q$ be a maximum directed path in $D$, starting on $u$, that is disjoint from $V(P) \setminus \{u\}$. Since $Q$ is maximum, the two out-neighbours of $\text{term}(Q)$ belong to $V(P) \cup V(Q)$. We have that the length of $Q$ is at most $\ell-1$, for otherwise the union of $P$ and $Q$ contains a copy of $S_2^{+(\ell)}$, a contradiction to the choice of $D$. This implies that the out-neighbourhood of $\text{term}(Q)$ is in $V(P) \setminus V(Q)$, for otherwise $D[V(Q)]$ contains a directed cycle of length at most $\ell-1$, a contradiction. Let $x$ be the out-neighbour of $Q$ which is the furthest from $u$ and $y$ be its other out-neighbour. Let $Q'$ be the extension of $Q$ with $x$, then $(Q')$ is a $P$-tricot of size one since $Q'$ starts at $u$, intersects $P$ exactly on $\{u, x\}$ and $y$ belongs to $P[u, x[$.

Among all $P$-tricots of $D$, we choose one with maximum size $r$ and denote it by $\mathcal{T}$. Let $P_1$ be the directed path corresponding to the concatenation of $Q_1$ and all $P[\text{term}(Q_{i-2}), \text{init}(Q_i)] \cdot Q_i$ for odd $i \in [r]$.
$\{3, \dots, r\}$. Let $P_2$ be the directed path corresponding to the concatenation of all $P[\text{term}(Q_{i-2}), \text{init}(Q_i)] \cdot Q_i$ for even $i \in \{2, \dots, r\}$ (we identify term($Q_0$) with $u$).

Observe that $P_1$ and $P_2$ are two directed paths starting from $u$, and that they intersect exactly on $\{u\}$. Note that $P_1$ can be completed into a $(u, w)$-path $\tilde{P}_1 = P_1 \cdot P[\text{term}(P_1), w]$ disjoint from $P_2 - \text{term}(P_2)$. Since it is a $(u, w)$-path, $\tilde{P}_1$ has length at least $\ell$. Therefore $P_2$ has length at most $\ell$, for otherwise $\tilde{P}_1 \cup (P_2 - \text{term}(P_2))$ is a copy of $S_2^{+(\ell)}$ in $D$. Analogously, $P_2$ can be completed into a $(u, w)$-path, which implies that $P_1$ has length at most $\ell$.

Let $i \in \{1, 2\}$ be such that $P_i$ does not contain $Q_r$ and let $j \in \{1, 2\}$ be different from $i$. Let $v$ be $\text{pred}_P(\text{term}(Q_r))$. We consider $Q'$ a maximal directed path starting from $v$ in $D - (V(P) \cup V(P_1) \cup V(P_2) \setminus \{v\})$. Let $t$ be term($Q'$), let $P'_i$ be the concatenation $P_i \cdot P[\text{term}(P_i), v] \cdot Q'$ and $P'_j$ be the concatenation $P_j \cdot P[\text{term}(Q_r), w]$. See Figure 5 for an illustration.

<figure><img src="image_5.png" /><figcaption>Figure 5: An illustration of the paths $P'_i$ and $P'_j$.</figcaption></figure>

Since $P'_j$ is a $(u, w)$-path, $P'_j$ has length at least $\ell$. If also $P'_i$ has length at least $\ell$, then $P'_i$ and $P'_j$ are two directed paths of length at least $\ell$, sharing their source $u$ and no other vertices, a contradiction since $D$ is a counterexample. We know that $t$ has two out-neighbours $x, y$ in $D$. Since $Q'$ is a maximal directed path, we know that both $x$ and $y$ belong to $V(P'_i) \cup V(P'_j) \cup V(P)$.

* First if one of $x, y$, say $x$, belongs to $V(P'_i)$, $P'_i[x, t] \cup \text{term}(P'_i)x$ is a directed cycle of length at most

$$ \text{length}(P'_i[x, t]) + 1 \le \text{length}(P'_i) + 1 \le \ell, $$

where in the last inequality we used that $P'_i$ has length at most $\ell - 1$. This is a contradiction since $\text{digirth}(D) \ge 2\ell > \ell - 1$.

* Else if one of $x, y$, say $x$, belongs to $V(P[u, v])$, then $P[x, v] \cdot Q' \cup tx$ is a directed cycle of length at most:

$$ \text{length}(P[x, v]) + \text{length}(Q'[v, t]) + 1 $$

$$ \le \text{length}(P[u, v]) + \text{length}(Q'[v, t]) + 1 \quad \text{because } u \text{ is before } x \text{ in } P $$

$$ \le \text{length}(P'_i[u, v]) + \text{length}(Q'[v, t]) + 1 \quad \text{because } P \text{ is a shortest path} $$

$$ = \text{length}(P'_i) + 1 \le \ell, $$

a contradiction since $\text{digirth}(D) \ge 2\ell > \ell$.

* Else if one of $x, y$, say $x$, belongs to $V(P_j) \setminus V(P[u, v])$, let $z$ be $\text{pred}_{P_j}(\text{term}(P_j))$, which is also $\text{pred}_{Q_r}(\text{term}(Q_r))$. By definition of $\mathcal{T}$, $z$ has an out-neighbour $s$ in $V(P)\text{init}(Q_r), \text{term}(Q_r)]$. Then
$P_j[x, z] \cdot zs \cdot P[s, v] \cdot Q' \cup tx$ is a directed cycle with length at most

$$
\begin{align*}
& \text{length}(P_j[x, z]) + \text{length}(P[s, v]) + \text{length}(Q') + 2 \\
& \le \text{length}(P_j) + \text{length}(P[s, v]) + \text{length}(Q') && \text{because } x \ne u \text{ and } z \ne \text{term}(P_j) \\
& \le \text{length}(P_j) + \text{length}(P'_i[u, v]) + \text{length}(Q') && \text{because } P \text{ is a shortest path} \\
& \le \text{length}(P_j) + \text{length}(P'_i) \le 2\ell - 1,
\end{align*}
$$

a contradiction since $\text{digirth}(D) \ge 2\ell$.

* Finally if both $x$ and $y$ belong to $P[\text{term}(Q_r), w]$, we can assume that $x$ is before $y$ on the path $P$. But then the $P$-tricot $(Q_1, \dots, Q_r, Q' \cdot ty)$ contradicts the maximality of $\mathcal{T}$.

□

# 7 Further research directions

In this work, for a fixed digraph $F$, we gave some sufficient conditions on a digraph $D$ to ensure that $D$ contains $F$ as a subdivision. This is just the tip of the iceberg and many open questions arise. In particular, the exact value of $\text{mader}_{\bar{\chi}}(F)$ is known only for very few graphs $F$. The smallest digraph $F$ for which it is unknown is $\overleftrightarrow{K_3}$.

**Conjecture 16** (Gishboliner, Steiner and Szabó [11]).

$$ \text{mader}_{\bar{\chi}}(\overleftrightarrow{K_3}) = 4 $$

In the first part of this paper, we looked for paths and cycles in large dicritical digraphs. In particular, we proved in Theorem 5 that for every integer $k \ge 3$, there are infinitely many $k$-dicritical digraphs without any directed path on $3k+1$ vertices. Conversely Bermond et al. [5] proved that every connected digraph with $\delta^+(D) \ge k$ and $\delta^-(D) \ge \ell$ contains a directed path of order at least $\min\{n, k+\ell+1\}$. As every vertex in a $k$-dicritical digraph has in- and out-degree at least $k-1$, we obtain that there are finitely many $k$-dicritical digraphs with no directed path on $2k-1$ vertices. The following problem then naturally comes.

**Problem 17.** For every integer $k \ge 3$, find the largest integer $f(k) \in [2k-1, 3k]$ such that the set of $k$-dicritical $\overrightarrow{P_{f(k)}}$-free digraphs is finite.

Given a digraph $F$, we say that $F$ is $\delta^+$-maderian if there is an integer $k$ such that every digraph $D$ with $\delta^+(D) \ge k$ contains a subdivision of $F$. The smallest such integer $k$ is then denoted by $\text{mader}_{\delta^+}(F)$. The problem of characterising $\delta^+$-maderian digraphs is widely open. In particular, Mader [18] conjectured that every acyclic digraph is $\delta^+$-maderian, but this remains unproven albeit many effort to prove or disprove it (see [16] for a partial answering to the conjecture).

In the remaining of the paper, we focused on digraphs of large digirth. Given a digraph $F$, and an integer $g$, we can define $\text{mader}_{\delta^+}^{(g)}(F)$ to be the smallest integer $k$, if it exists, such that every digraph $D$ with $\delta^+(D) \ge k$ and $\text{digirth}(D) \ge g$ contains a subdivision of $F$.

It is interesting to note that there are digraphs which are not $\delta^+$-maderian even when restricted to digraphs of large digirth. Indeed, for every integers $g, d$ there is a digraph $D$ with $\text{digirth}(D) \ge g$ and $\delta^+(D) \ge d$ such that $D$ does not contains any subdivision of $\overleftrightarrow{K_3}$. Such a digraph $D$ can be easily obtained from a construction by DeVos et al. [8] of digraphs with arbitrarily large out-degree in which every directed cycle has odd length, by removing a few arcs in order to increase the digirth. Since every subdivision of $\overleftrightarrow{K_3}$ has an even directed cycle, such a digraph does not contain $\overleftrightarrow{K_3}$ as a subdivision.

In Theorem 11, we proved that $\text{mader}_{\delta^+}^{(8k-4)}(C(k, k)) \le 2$. On the other hand, the value $8k-4$ can not be replaced by $k-1$. To see this, consider the digraph with vertex set $\mathbb{Z}/(2k-1)\mathbb{Z}$ and arc set $\{(i, i+1), (i, i+2) \mid i \in V(G)\}$. Since $|V(D)| < 2k$, $D$ has no subdivision of $C(k, k)$. Since $\delta^+(D) = 2$ and $\text{digirth}(G) = k-1$, we deduce that $\text{mader}_{\delta^+}^{(k-1)}(C(k, k)) > 2$. Thus the following problem arises.
**Problem 18.** Find the minimum $g \in [k, 8k - 4]$ such that $\mathrm{mader}_{\delta^+}^{(g)}(C(k, k)) \le 2$.

In this paper, we studied the value of $\min\{\mathrm{mader}_{\chi}^{(g)}(X) | g \ge 0\}$ given a digraph $X$. Actually, we believe that this value is upper bounded by a function of the maximum degree.

**Conjecture 19.** There is a function $f$ such that for every digraph $F$ with maximum degree $\Delta$, there is an integer $g$ such that $\mathrm{mader}_{\tilde{\chi}}^{(g)}(F) \le f(\Delta)$.

This is motivated by the following result by Mader [19], which is somehow the undirected analog of Conjecture 19.

**Theorem 20 (Mader [19]).** There is a function $f$ such that for every graph $F$, for every graph $G$ with $\delta(G) \ge \max\{\Delta(F), 3\}$, if girth$(G) \ge f(F)$ then $G$ contains a subdivision of $F$.

It was later proved by Kühn and Osthus [14] that one can take $f(H) = 166 \frac{\log|V(H)|}{\log \Delta(H)}$, which is optimal up to the constant factor.

Harutyunyan and Mohar [12] proved that there is a positive constant $c$ such that for every large enough $\Delta$, $g$, there is a digraph $D$ with girth$(D) \ge g$, $\Delta(D) \le \Delta$ and $\tilde{\chi}(D) \ge c \cdot \frac{\Delta}{\log \Delta}$. This is a generalisation to the directed case of a classical result by Bollobás [7]. This implies that any function $f$ satisfying Conjecture 19 is such that $f(\Delta) \ge c \cdot \frac{\Delta}{\log \Delta}$. We are inclined to believe that this is optimal and that there is such a function $f$ in $O\left(\frac{\Delta}{\log \Delta}\right)$.

## Acknowledgement

We are grateful to Frédéric Havet for stimulating discussions and valuable advice.

## References

[1] P. Aboulker, N. Cohen, F. Havet, W. Lochet, P. F. S. Moura, and S. Thomassé. Subdivisions in digraphs of large out-degree or large dichromatic number. *The Electronic Journal of Combinatorics*, 26(3), July 2019.

[2] N. Alon, M. Krivelevich, and P. Seymour. Long cycles in critical graphs. *Journal of Graph Theory*, 35(3):193–196, 2000.

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

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

[5] J.-C. Bermond, A. Germa, M.-C. Heydemann, and D. Sotteau. Longest paths in digraph. *Combinatorica*, 1(4), 1981.

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

[7] B. Bollobás. Chromatic number, girth and maximal degree. *Discrete Mathematics*, 24(3):311–314, 1978.

[8] M. DeVos, J. McDonald, B. Mohar, and D. Scheide. Immersing complete digraphs. *European Journal of Combinatorics*, 33(6):1294–1302, 2012.

[9] T. Gallai. Kritische Graphen I. *Publications of the Mathematical Institute of the Hungarian Academy of Sciences*, 8:165–192, 1963.

[10] T. Gallai. Kritische Graphen II. *Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei*, 8:373–395, 1963.
[11] L. Gishboliner, R. Steiner, and T. Szabó. Dichromatic number and forced subdivisions. *Journal of Combinatorial Theory, Series B*, 153:1–30, Mar. 2022.

[12] A. Harutyunyan and B. Mohar. Two results on the digraph chromatic number. *Discrete Mathematics*, 312(10):1823–1826, 2012.

[13] J. B. Kelly and L. Kelly. Paths and circuits in critical graphs. *American Journal of Mathematics*, 76(4):786–792, 1954.

[14] D. Kühn and D. Osthus. Topological minors in graphs of large girth. *Journal of Combinatorial Theory, Series B*, 86(2):364–380, 2002.

[15] O. Kwon and X. Lian. On a variant of dichromatic number for digraphs with prescribed sets of arcs. *arXiv preprint arXiv:2307.05897*, 2023.

[16] W. Lochet. Immersion of transitive tournaments in digraphs with large minimum outdegree. *Journal of Combinatorial Theory, Series B*, 134:350–353, 2019.

[17] L. Lovász. *Combinatorial problems and exercises*, volume 361. American Mathematical Society, 2007.

[18] W. Mader. Degree and local connectivity in digraphs. *Combinatorica*, 5(2):161–165, 1985.

[19] W. Mader. Topological subgraphs in graphs of large girth. *Combinatorica*, 18(3):405–412, 1998.

[20] A. Shapira and R. Thomas. Color-critical graphs have logarithmic circumference. *Advances in Mathematics*, 227(6):2309–2326, 2011.

[21] R. Steiner. Subdivisions with congruence constraints in digraphs of large chromatic number. *Journal of Graph Theory*, 105(1):136–143, 2024.