# Digraph Colouring and Arc-Connectivity

Pierre Aboulker  DIENS, École normale supérieure, CNRS, PSL University, Paris,
France.  Guillaume Aubian  DIENS, École normale supérieure, CNRS, PSL
University, Paris, France.  Université de Paris, CNRS, IRIF, F-75006, Paris,
France.  Pierre Charbit  Université de Paris, CNRS, IRIF, F-75006, Paris,
France.

###### Abstract

The dichromatic number $\operatorname{\overrightarrow{\chi}}(D)$ of a digraph
$D$ is the minimum size of a partition of its vertices into acyclic induced
subgraphs. We denote by $\lambda(D)$ the maximum local arc connectivity of a
digraph $D$. Neumann-Lara proved that for every digraph $D$,
$\operatorname{\overrightarrow{\chi}}(D)\leq\lambda(D)+1$. In this paper, we
characterize the digraphs $D$ for which
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1$. This generalizes an
analogue result for undirected graphs proved by Stiebitz and Toft as well as
the directed version of Brooks’ Theorem proved by Mohar. Along the way, we
introduce a generalization of Hajós join that gives a new way to construct
families of dicritical digraphs that is of independent interest.

###### Contents

  1. 1 Introduction
    1. 1.1 The undirected case
    2. 1.2 Our result: the directed case
  2. 2 Definitions
  3. 3 Tools
  4. 4 First properties of $k$-extremal digraphs
  5. 5 Directed Hajós joins and Hajós bijoins - A First Decomposition Theorem
    1. 5.1 Properties of directed Hajós joins
    2. 5.2 Properties of Hajós bijoin
    3. 5.3 Proof of Theorem 5.1
  6. 6 Hajós tree joins - Structure Theorems
  7. 7 Recognition algorithm
  8. 8 The hypergraph case
  9. 9 $2$-extremal digraphs

##  1 Introduction

The dichromatic number $\operatorname{\overrightarrow{\chi}}(D)$ of a digraph
$D$ is the least integer $k$ such that $D$ can be partitioned into $k$ acyclic
digraphs.

The dichromatic number was first introduced by Neumann-Lara [28] in 1982 and
was rediscovered by Mohar [26] 20 years later. It is easy to see that for any
undirected graph $G$, the symmetric digraph $\overleftrightarrow{G}$ obtained
from $G$ be replacing each edge by a digon satisfies
$\chi(G)=\operatorname{\overrightarrow{\chi}}(\overleftrightarrow{G})$. This
simple fact permits to generalize results on the chromatic number of
undirected graphs to digraphs via the dichromatic number. Such results have
(recently) been found in various areas of graph colouring such as extremal
graph theory [3, 18, 20], algebraic graph theory [27], substructure forced by
large dichromatic number [2, 5, 6, 9, 11, 15, 33], list dichromatic number [8,
13], dicolouring digraphs on surfaces [7, 21, 31], flow theory [17, 19], links
between dichromatic number and girth [16, 32], complexity [14]. Thus, more and
more efforts are made to extend colouring results from undirected graphs to
directed graphs. This paper participates in this effort. We explain the
undirected version of our result in the next section. The reader in a hurry
who would like to read our result directly can jump to Section 1.2.

###  1.1 The undirected case

Let $G$ be a graph. The chromatic number $\chi(G)$ of $G$ is the least integer
$k$ such that $G$ can be partitioned into $k$ stable sets. A graph is
$k$-critical if it has chromatic number $k$ and all its proper subgraphs have
chromatic number at most $k-1$.

It is an easy observation that, for every graph $G$, $\chi(G)\leq\Delta(G)+1$,
where $\Delta(G)$ is the maximum degree of $G$. Moreover, equality holds for
odd cycles and complete graphs, and the chromatic number of a graph equals the
maximum chromatic number of its connected components. This leads to a full
characterization of graphs $G$ for which $\chi(G)=\Delta(G)+1$, famously known
as Brooks’ Theorem. Let $\mathcal{B}_{2}$ be the set of odd cycles and for
$k\neq 2$, let $\mathcal{B}_{k}=\\{K_{k+1}\\}$.

######  Theorem 1.1 (Brooks’ Theorem [10]).

Let $G$ be a graph. Then $\chi(G)=\Delta(G)+1=k+1$ if and only if one of the
connected component of $G$ is in $\mathcal{B}_{k}$.

Given two vertices $u,v$ of a graph $G$, $\lambda(u,v)$ is the maximum number
of edge-disjoint paths linking $u$ and $v$, and $\lambda(G)$ is the maximum
local edge connectivity of $G$, that is $\max_{u\neq v}\lambda(u,v)$. Mader
[24] proved that for every graph $G$, $\chi(G)\leq\lambda(G)+1$. Moreover, it
is clear that $\lambda(G)\leq\Delta(G)$. Thus, for every graph $G$,

$\chi(G)\leq\lambda(G)+1\leq\Delta(G)+1$

Hence one can ask for graphs $G$ for which

$\chi(G)=\lambda(G)+1$ (1)

Exception of Brooks’ Theorem of course satisfies (1), but it turns out that
there are more.

To describe them, we need a famous construction first introduced by Hajós [12]
to construct an infinite family of $k$-critical graphs. Let $G_{1}$ and
$G_{2}$ be two graphs, with $uv_{1}\in E(G_{1})$ and $v_{2}w\in E(G_{2})$. The
Hajós join of $G_{1}$ and $G_{2}$ with respect to $(uv_{1},v_{2}w)$ is the
graph $G$ obtained from the disjoint union of $G_{1}-uv_{1}$ and
$G_{2}-v_{2}w$, by identifying $v_{1}$ and $v_{2}$ to a new vertex $v$, and
adding the edge $uw$.

An odd wheel, is a graph obtained from an odd cycle by adding a vertex
adjacent to every vertex of the odd cycle. Note that $K_{4}$ is an odd wheel
and that odd wheels satisfy (1).

One can prove that the Hajós join $G$ of two graphs $G_{1}$ and $G_{2}$
satisfies (1) if and only if both $G_{1}$ and $G_{2}$ satisfies it. Moreover,
the maximum local edge connectivity of a graph equal the maximum maximum local
edge connectivity of its blocks.

This leads to the characterization of graphs $G$ satisfying (1), proved by
Aboulker et al. [4] for graphs $G$ with $\chi(G)\leq 4$, and by Stiebitz and
Toft [34] for $\chi(G)\geq 5$.

Let $\mathcal{H}_{k}=\mathcal{B}_{k}$ when $k\leq 2$, let $\mathcal{H}_{3}$ be
the smallest class containing all odd wheels and closed under taking Hajós
join, and for $k\geq 4$, let $\mathcal{H}_{k}$ be the smallest class of graphs
containing $K_{k}$ and closed under taking Hajós join.

######  Theorem 1.2 ([34]).

Let $G$ be a graph. Then $\chi(G)=\lambda(G)+1=k+1$ if and only if a block of
$G$ is in $\mathcal{H}_{k}$.

The goal of this paper is to generalize this result to digraphs.

This result has already been generalized for hypergraphs and our result can be
compared to the hypergraph case as we explain in Section 8.

###  1.2 Our result: the directed case

Brooks’ Theorem has been generalized to digraphs by Mohar [27]. There are
several notions of maximum degree for a digraph. The most suitable one to
generalize Brooks’ theorem is the following: Given a digraph $D$, let
$\Delta_{max}(D)$ be the maximum over the vertices of $G$ of the maximum of
their in-degree and their out-degree.

It is an easy observation that
$\operatorname{\overrightarrow{\chi}}(D)\leq\Delta_{max}(D)+1$. Moreover,
equality holds for directed cycles, symmetric odd cycles and symmetric
complete graphs. Finally, the dichromatic number of a digraph $D$ is the
maximum dichromatic number of its connected components, where the connected
components of a digraph are the connected components of its underlying graph.
This leads to the directed Brooks’ Theorem.

Let $\vec{\mathcal{B}}_{1}$ be the set of directed cycles, let
$\vec{\mathcal{B}}_{2}$ be the set of symmetric odd cycles and, for $k=0$ and
$k\geq 3$, let $\vec{\mathcal{B}}_{k}=\\{\overleftrightarrow{K}_{k+1}\\}$.

######  Theorem 1.3 (Directed Brooks’ theorem [27], see also [1]).

Let $D$ be a digraph. Then
$\operatorname{\overrightarrow{\chi}}(D)=\Delta_{max}(D)+1=k+1$ if and only if
a connected component of $D$ is in $\vec{\mathcal{B}}_{k}$

Let $D$ be a digraph. Given a pair of ordered vertices $(u,v)$, we denote by
$\lambda(u,v)$ the maximum number of arc-disjoint directed paths from $u$ to
$v$, and by $\lambda(D)$ the maximum local arc-connectivity of $D$, that is
$max_{u\neq v}\lambda(u,v)$. Neumann-Lara [28] proved that for every digraph
$D$, $\operatorname{\overrightarrow{\chi}}(D)\leq\lambda(D)+1$. Since we
clearly have that $\lambda(D)+1\leq\Delta_{max}(D)+1$, we get that for every
digraph $D$:

$\operatorname{\overrightarrow{\chi}}(D)\leq\lambda(D)+1\leq\Delta_{max}(D)+1$

The main result of this paper is a full characterization of digraphs $D$ for
which

$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1$ (2)

when $\operatorname{\overrightarrow{\chi}}(D)\leq 2$ and
$\operatorname{\overrightarrow{\chi}}(D)\geq 4$. This generalizes the directed
Brooks’ Theorem and Theorem 1.2 except for digraphs with dichromatic number
$3$ that we have not been able to characterize. See Section 9.

There are two easy observations one can make about digraphs that satisfy (2).
First, a digraph satisfies
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$ if and only if one
of its strong component $S$ satisfies
$\operatorname{\overrightarrow{\chi}}(S)=\lambda(S)+1=k+1$. Indeed, the
dichromatic number of a digraph is equal to the maximum dichromatic number of
its strong components, the maximum local arc-connectivity of a digraph is at
least the maximum local arc-connectivity of its strong components, and for
every digraph, $\operatorname{\overrightarrow{\chi}}$ is at most $\lambda+1$.
Second, and for the same exact reason, if a digraph $D$ is strong but has
cutvertices, then $D$ satisfies
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$ if and only if one
of its block $B$ satisfies
$\operatorname{\overrightarrow{\chi}}(B)=\lambda(B)+1=k+1$. Note that these
blocks also induce strong digraphs.

Thus, our main theorem will be a structural characterization of the class of
$k$-extremal digraphs (for $k=1$ and $k\geq 3$) where a digraph $D$ is
$k$-extremal if $D$ is strong, its underlying graph is $2$-connected, and
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$.

Characterizing $1$-extremal digraphs is rather easy, we will prove in Section
4 (Theorem 4.2) that they are exactly the class of directed cycles. Studying
$k$-extremal digraphs for larger values of $k$ requires more engineering.
Mimicking the construction appearing in Theorem 1.2, we need to develop an
analogue of Hajós joins for digraphs. As a matter of fact, we will need a wild
generalization of Hajós join, giving a new way to construct $k$-dicritical
digraphs that is interesting on its own.

The most natural way to generalize Hajós join is to take the same definition,
and replace edges by digons. Given two vertices $u$ and $v$, we set
$[u,v]=\\{uv,vu\\}$.

######  Definition 1.4 (Bidirected Hajós join).

Let $D_{1}$ and $D_{2}$ be two digraphs, with $[u,v_{1}]\subseteq A(D_{1})$
and $[v_{2},w]\subseteq A(D_{2})$. The bidirected Hajós join of $D_{1}$ and
$D_{2}$ with respect to $([u,v_{1}],[w,v_{2}])$ is the digraph $D$ obtained
from the disjoint union of $D_{1}-[u,v_{1}]$ and $D_{2}-[w,v_{2}]$, by
identifying $v_{1}$ and $v_{2}$ to a new vertex $v$, and adding the digon
$[u,w]$.

Bidirected Hajós joins were first introduced and studied in [3].

Still inspired by the Hajós joins, the so-called directed Hajós join, first
introduced in [18] and studied in [3] is defined as follows. See Figure 1.

######  Definition 1.5 (Directed Hajós join).

Let $D_{1}$ and $D_{2}$ be two digraphs, with $uv_{1}\in A(D_{1})$ and
$v_{2}w\in A(D_{2})$. The directed Hajós join of $D_{1}$ and $D_{2}$ with
respect to $(uv_{1},v_{2}w)$ is the digraph $D$ obtained from the disjoint
union of $D_{1}-uv_{1}$ and $D_{2}-v_{2}w$, by identifying $v_{1}$ and $v_{2}$
to a new vertex $v$, and adding the arc $uw$.

$v$$w$$u$$u$$v_{1}$$D_{1}$$w$$v_{2}$$D_{2}$$D$ Figure 1: $D$ is a directed
Hajós join of $D_{1}$ and $D_{2}$.

These two operations are particularly interesting because one can prove that
the bidirected (directed) Hajós join $D$ of two digraphs $D_{1}$ and $D_{2}$
is $k$-dicritical if and only if both $D_{1}$ and $D_{2}$ are $k$-dicritical.
They, therefore, provide a way to construct an infinite family of
$k$-dicritical digraphs. They are also primordial for us because $D$ satisfies
(2) if and only if both $D_{1}$ and $D_{2}$ do. Thus, they also provide a way
to construct an infinite family of digraphs satisfying (2).

But these two joins are not enough to capture all digraphs satisfying (2). In
order to do so, we need to define Hajós tree joins, which can be seen as a
generalization of bidirected Hajós joins. See Figure 2.

######  Definition 1.6 (Hajós tree join and Hajós star join).

Given

  * •

a tree $T$ embedded in the plane with edges
$\\{u_{1}v_{1},\dots,u_{n}v_{n}\\}$,

  * •

a circular ordering $C=(x_{1},\dots,x_{\ell})$ of the leaves of $T$, taken
following the natural ordering given by the embedding of $T$, and

  * •

for $i=1,\dots,n$, a digraph $D_{i}$ such that

    * –

$V(D_{i})\cap V(T)=\\{u_{i},v_{i}\\}$,

    * –

$[u_{i},v_{i}]\subseteq A(D_{i})$, and

    * –

for $1\leq i\neq j\leq n$, $V(D_{i})\setminus\\{u_{i},v_{i}\\}\cap
V(D_{j})\setminus\\{u_{j},v_{j}\\}=\emptyset$,

we define the Hajós tree join $T(D_{1},\dots,D_{n};C)$ to be the digraph
obtained from $D_{i}-[a_{i},b_{i}]$ for $i=1,\dots,n$ by adding the directed
cycle $C=x_{1}\rightarrow x_{2}\rightarrow\dots\rightarrow x_{\ell}\rightarrow
x_{1}$.

$C$ is called the peripheral cycle of $D$ and vertices
$u_{1},v_{1},\dots,u_{n},v_{n}$ are the junction vertices of $D$ (note that
there are $n+1$ of them).

When $T$ is a star, we call it Hajós star join.

$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$T$$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$G_{1}$$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$G_{2}$$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$G_{3}$
Figure 2: $T$ is a tree, and $G_{1}$ illustrates the general shape of a Hajós
tree join built from $T$. Each block represents one of the $D_{i}$, where the
removed digons corresponding to the edges of $T$ are drawn with dotted green.
The circular ordering is $(a,b,h,i,d)$, it follows the natural ordering given
by the embedding of $T$. $G_{2}$ is the same as $G_{1}$ where each of the
$D_{i}$ is $\overleftrightarrow{K}_{4}$ minus a digon. We have that
$\operatorname{\overrightarrow{\chi}}(G_{2})=\lambda(G_{2})+1=4$. Finally,
$G_{3}$ shows the importance of taking a circular ordering corresponding to an
embedding of $T$ for the peripheral cycle. Indeed, for $G_{3}$, the ordering
is $(a,b,i,h,d)$ which does not correspond to any embedding of $T$. Observe
that $\operatorname{\overrightarrow{\chi}}(G_{3})=4<\lambda(G_{3})+1=5$. To
see that $\lambda(G_{3})=4$, observe that there are four (coloured) arc-
disjoint $eg$-dipaths.

Note that, when $T$ is the path on three vertices, we recover a bidirected
Hajós join.

The basic idea of the Hajós tree join is the following: if each $D_{i}$ is
$k$-dicritical, then any $(k-1)$-dicolouring of $D_{i}-[a_{i},b_{i}]$ give the
same colour to $a_{i}$ and $b_{i}$, which implies that in any
$(k-1)$-dicolouring of $D-A(C)$, all the junction vertices receive the same
colour, and thus $D$ is not $(k-1)$-dicolourable. Actually, we can prove that
$D$ satisfies (2) if and only each of the $D_{i}$ does. Hence, Hajós tree join
also provides a way to construct an infinite family of digraphs satisfying
(2).

######  Definition 1.7 (The classes $\mathcal{H}_{k}$).

Let $\vec{\mathcal{H}}_{3}$ be the smallest class of digraphs containing all
bidirected odd wheels and closed under taking directed Hajós joins and Hajós
tree joins, and for $k\geq 4$, let $\vec{\mathcal{H}}_{k}$ be the smallest
class of digraphs containing $\overleftrightarrow{K}_{k+1}$ and closed under
taking directed Hajós joins and Hajós tree joins.

The main result of this paper is:

######  Theorem 1.8.

Let $k\geq 3$. Let $D$ be a digraph with $\lambda(D)=k$. Then
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$ if and only if a
block of a strong component of $D$ is in $\vec{\mathcal{H}}_{k}$.

We also describe an algorithm that decides in polynomial time if a digraph $D$
belongs to $\vec{\mathcal{H}}_{k}$.

The rest of the paper is organized as follows. In Section 2 we give all the
needed definitions. In Section 3, we state a few basic tools needed for our
proofs. In Section 4 we prove several important structural properties of
$k$-extremal digraphs. In Section 5 we prove a first step towards the main
theorem by giving a decomposition theorem for $k$-extremal digraphs, and in
Section 6 we give the final proof of Theorem 1.8. In Section 7 we give a
polynomial time algorithm to recognize $k$-extremal digraphs. In section 8 we
discuss an analogue of our main result for hypergraphs, and in the last
section, we discuss the case of $2$-extremal digraphs and propose a conjecture
for their characterization.

##  2 Definitions

A directed graph, or digraph, is a pair $D=(V,A)$ of finite sets such that $A$
is a subset of $(V\times V)\setminus\\{(v,v)\mid v\in V\\}$. Thus our digraphs
contain no loops nor parallel arcs. They may contain digons, that is a pair of
arcs in opposite directions between the same vertices. The digon $\\{xy,yx\\}$
is denoted by $[x,y]$. We say that two vertices $x$ and $y$ are adjacent if
$xy$ or $yx$ is in $A(D)$. Given an undirected graph $G$, the symmetric
digraph $\overleftrightarrow{G}$ is the digraph obtained by replacing each
edge of $G$ with two arcs, one in each direction (a digon).

We sometimes write $x\rightarrow y$ when $xy\in A(D)$. A trail of a digraph
$D$ is a sequence of vertices $x_{1}x_{2}\ldots x_{p}$ such that
$x_{i}x_{i+1}\in A(D)$ for each $i<p$ and each arc is used once (but vertices
can be used several times). It is closed if $x_{1}=x_{p}$. A trail (resp.
closed trail) in which vertices are pairwise distinct is called a directed
path or dipath for short (resp. directed cycle or dicycle for short). A
$xy$-dipath is a dipath with first vertex $x$ and last vertex $y$.

Let $G$ be a connected undirected graph. A vertex $v\in V(G)$ is a cutvertex
if $G\setminus v$ is not connected. $G$ is $2$-connected (or biconnected) if
it is connected and has no cutvertex. A block of $G$ is a maximal biconnected
subgraph of $G$. These definitions are extended to digraphs where they are
applied to the underlying graphs, where the underlying graph of a digraph $D$
is the undirected graph on the same vertex set as $D$, where edges connect
vertices that are adjacent in $D$.

A digraph is strong, or strong, if for every pair of vertices $x$ and $y$,
there exists a $xy$-dipath and a $yx$-dipath.

An eulerian digraph is a digraph where for every vertex the outdegree is equal
to its indegree.

The local arc-connectivity $\lambda_{D}(x,y)$ of two distinct vertices $x$ and
$y$ is the maximum number of pairwise arc-disjoint $xy$-dipaths. When it is
clear from context, we omit the subscript $D$ and write $\lambda(x,y)$ instead
of $\lambda_{D}(x,y)$. The maximum local arc-connectivity $\lambda(D)$ of a
digraph $D$ is the maximum local arc-connectivity over all pairs of distinct
vertices.

Let $X\subseteq V$. We denote by $\overline{X}$ the set $V-X$. We denote by
$\partial^{+}(X)$ the set of arcs from $X$ to $\overline{X}$. A dicut
$(X,\overline{X})$ with $X\neq\emptyset$ and $X\neq V$ is the set of arcs
$\partial^{+}(X)$ and we say that $(X,\overline{X})$ has size $k$ if
$|\partial^{+}(X)|=k$. If $x\in X$ and $y\in\overline{X}$, we say that the
dicut $(X,\overline{X})$ separates $x$ from $y$, or that $(X,\overline{X})$ is
an $xy$-dicut. We say that $(X,\overline{X})$ isolates a vertex if $X$ or
$\overline{X}$ is a singleton.

Let $D$ be a digraph. If $u,v\in V(D)$, we denote as $D+uv$ the digraph
$(V(D),A(D)\cup\\{uv\\})$. Similarly, $D-uv=(V(D),A(D)\setminus\\{uv\\})$.

Let $k\geq 1$. We denote by [k] the set $\\{1,2,\dots,k\\}$. A
$k$-dicolouring, of a digraph $D$ is a function $\varphi:V(D)\rightarrow[k]$
such that the digraph induced by $\varphi^{-}1(i)$ is acyclic for every
$i\in[k]$. The dichromatic number $\operatorname{\overrightarrow{\chi}}(D)$ of
$D$ is the minimum $k$ such that $D$ is $k$-dicolourable. We will sometimes
extend $\operatorname{\overrightarrow{\chi}}$ to subsets of vertices, using
$\operatorname{\overrightarrow{\chi}}(X)$ to mean
$\operatorname{\overrightarrow{\chi}}(D[X])$ where $X\subseteq V(D)$. It is
easy to see that for any undirected graph $G$, we have
$\chi(G)=\operatorname{\overrightarrow{\chi}}(\overleftrightarrow{G})$.

We say that a digraph $D$ is $k$-dicritical if it has chromatic number $k$ for
some integer $k$ but the removal of any arc yields a digraph of dichromatic
number $k-1$. Similarly, a digraph $D$ is $k$-vertex-dicritical if it has
dichromatic number $k$ for some integer $k$ but the removal of any vertex
yields a digraph of dichromatic number $k-1$.

A digraph $D$ is $k$-extremal if it is biconnected, strong and
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$.

##  3 Tools

In [25], Menger proved the following fundamental result connecting dicuts and
arc-disjoint dipaths:

######  Theorem 3.1 (Menger Theorem [25]).

Let $D$ be a directed digraph and let $u,v\in V(D)$ be a pair of distinct
vertices. Then $\lambda(u,v)=\partial^{+}(U)$ where $(U,\overline{U})$ is a
minimum dicut separating $u$ from $v$.

Lovász [23] proved the following result:

######  Theorem 3.2 (Lovász [23]).

Let $D$ be a digraph in which $\lambda(x,y)=\lambda(y,x)$ for any $x,y\in
V(D)$. Then $D$ is Eulerian.

The next lemma is crucial as it can be applied to describe the structure of
minimum dicuts in $k$-extremal digraphs.

######  Lemma 3.3.

Let $k\geq 1$. Let $D$ be a digraph such that
$\operatorname{\overrightarrow{\chi}}(D)\geq k+1$. Let $(X_{1},X_{2})$ be a
dicut of $D$ of size at most $k$ such that $D[X_{1}]$ and $D[X_{2}]$ are both
$k$-dicolourable, and let $\phi_{1}$ (resp. $\phi_{2}$) a $k$-dicolouring of
$D[X_{1}]$ (resp. $D[X_{2}]$). Then the following holds :

  * •

either there exists a unique color $i$ such that vertices in
$\phi_{1}^{-1}(i)$ have outneighbours in $X_{2}$. In this case for every
$1\leq j\leq k$ there is exactly one arc from a vertex in $\phi_{1}^{-1}(i)$
to a vertex in $\phi_{2}^{-1}(j)$, and at least one arc from
$\phi_{2}^{-1}(j)$ to $\phi_{1}^{-1}(i)$,

  * •

or symmetrically there exists a unique color $j$ such that vertices in
$\phi_{2}^{-1}(j)$ have in-neighbours in $X_{1}$. In this case for every
$1\leq i\leq k$ there is exactly one arc from a vertex in $\phi_{1}^{-1}(i)$
to a vertex in $\phi_{2}^{-1}(j)$, and at least one arc from
$\phi_{2}^{-1}(j)$ to $\phi_{1}^{-1}(i)$.

In particular $(X_{1},X_{2})$ has size exactly $k$.

Consequently, if $(X_{2},X_{1})$ also has size at most $k$, then the cut has
exactly $k$ arcs in both directions, and for any two $k$-dicolouring of the
two sides the following holds : on one side all arcs through the cut are
incident to the same colour class, and on the other side every colour class is
incident to exactly one arc in each direction through the cut.

###### Proof.

Let $B$ be the bipartite graph with parts $U_{1}=\\{1,\dots,k\\}$ and
$U_{2}=\\{1,\dots,k\\}$ where an edge $ij$ is present if and only if there
exists in the cut $(X_{1},X_{2})$ one ac in each direction between
$\phi_{1}^{-}1(i)$ and $\phi_{2}^{-}1(j)$. Note that by construction, there is
an injection from $E(B)$ to the set of arcs from $X$ to $\overline{X}$, so
that $|E(B)|\leq k$.

Let $H$ be the complement of $B$, that is $V(H)=V(B)$ and $E(H)=\\{ij\mid i\in
U,j\in V,ij\notin E(B)\\}$. Observe that if $i\in U$, $j\in V$ and $ij\in
E(H)$, then in $D$ there cannot be a directed cycle which uses only color $i$
in $X_{1}$ and color $j$ in $X_{2}$ since this would imply the existence of an
arc in each direction between $\phi_{1}^{-}1(i)$ and $\phi_{2}^{-}1(j)$.

First suppose by contradiction that $H$ has a perfect matching $M$ and hence
there exists a permutation $\sigma$ such that $i\sigma(i)\in E(H)$ for every
$i\in[1,k]$. Let $\varphi:V(D)\rightarrow[k]$ be defined as follows:

$\varphi(x)=\begin{cases}\phi_{1}(x),&\text{if}\ x\in X_{1}\\\
\sigma(\phi_{2}(x)),&\text{if}\ x\in X_{2}\end{cases}$ (3)

By the previous observation, $\varphi$ is a $k$-dicolouring of $D$, a
contradiction.

Thus, $H$ has no perfect matching. By Hall’s marriage theorem, there is
$Z\subseteq U$ such that $|N_{H}(Z)|<|Z|$. Thus, there are all possible edges
between $Z$ and $V-N_{H}(Z)$ and by counting the number of these edges we get:

$\displaystyle k\geq|E(B)|$ $\displaystyle\geq|Z|(k-|N_{H}(Z)|)$
$\displaystyle\geq|Z|(k-(|Z|-1))$

Hence $|Z|(k-(|Z|-1))-k=(k-|Z|)(|Z|-1)\leq 0$. But as $1\leq|Z|\leq k$, we
have that $|Z|=1$ or $|Z|=k$. The first case corresponds to a vertex in
$U_{1}$ with no neighbour in $U_{2}$ in $H$, so adjacent to all of $U_{2}$ in
$B$. And the second case implies that one vertex in $U_{2}$ is not adjacent to
any neighbour of $U_{1}$ in $H$, and therefore adjacent to every vertex of
$U_{1}$ in $B$. Since $(X_{1},X_{2})$ has at most $k$ arcs, it is easy to see
that in $D$ these two cases exactly correspond to the two outcomes in the
Lemma.

The last statement of the lemma easily follows by applying the argument in
both directions. ∎

From the previous Lemma we derive the following corollary.

######  Corollary 3.4.

Let $D$ be a digraph. If $D$ has a dicut $(X_{1},X_{2})$ of size at most
$k-1$, and $\operatorname{\overrightarrow{\chi}}(D[X_{i}])\leq k$ for $i=1,2$,
then $\operatorname{\overrightarrow{\chi}}(D)\leq k$.

Note that by induction on the number of vertices (and since
$\lambda(D^{\prime})\leq\lambda(D)$ if $D^{\prime}$ is a subdigraph of $D$),
this corollary (applied with $k=\lambda(D)+1$) implies Neumann’s Lara theorem
that $\operatorname{\overrightarrow{\chi}}(D)\leq\lambda(D)+1$ for any digraph
$D$.

When proving that some digraphs have small maximum local edge connectivity, we
will often use the following Lemma:

######  Lemma 3.5.

Let $D$ be a digraph, $u\neq v\in V(D)$ and $P$ a $uv$-dipath. Then
$\lambda(D+uv-A(P))\leq\lambda(D)$.

###### Proof.

Let $H=D+uv-A(P)$. Assume for contradiction that there exist $x,y\in V(D)$
that are linked by $\lambda(D)+1$ arc-disjoint $xy$-dipaths. Since these
dipaths cannot all exist in $D$, one of them contains the arc $uv$. Then, by
replacing $uv$ by $P$, we obtain $\lambda(D)+1$ arc-disjoint $xy$-dipaths in
$D$, a contradiction. ∎

##  4 First properties of $k$-extremal digraphs

Recall that a digraph $D$ is $k$-extremal if it is biconnected, strong and
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$. The following
lemma proves easy but fundamental properties of $k$-extremal digraphs that
will be used constantly in the proofs.

######  Lemma 4.1.

Let $k\geq 1$, and let $D$ be a $k$-extremal digraph. Then $D$ is Eulerian,
$(k+1)$-dicritical and $\lambda(x,y)=k$ for every pair of distinct vertices
$x$ and $y$. In particular, if $(X,\overline{X})$ is a minimum dicut, then so
is $(\overline{X},X)$.

###### Proof.

Let $D$ be a $k$-extremal digraph, and assume $D$ is a minimal counter-
example.

We first prove that $D$ is $(k+1)$-vertex-dicritical. We proceed by
contradiction. Let $X\subsetneq V(D)$ be minimal such that
$\operatorname{\overrightarrow{\chi}}(D[X])=k+1$. By minimality of $X$, $D[X]$
is biconnected and strong. Moreover, since
$k+1=\operatorname{\overrightarrow{\chi}}(D[X])\leq\lambda(D[X])+1\leq\lambda(D)+1\leq
k+1$, we have $\lambda(D[X])=k$. So $D[X]$ is $k$-extremal and thus, by
minimality of $D$, $\lambda_{D[X]}(u,v)=k$ for every pair of distinct vertices
$u$, $v$ in $X$.

Let $x\in X$ such that $x$ has an outneighbour in $\overline{X}$ (it exists
because $D$ is strong). Let $R^{+}(x)$ (resp. $R^{-}(x)$) be the set of
vertices $y\in V(D)\setminus X$ such that there is a $xy$-dipath (resp. a
$yx$-dipath) with vertices in $\overline{X}\cup\\{x\\}$. Let $y\in R^{+}(x)$.
Since $D$ is strong, there exists a shortest dipath $P$ from $y$ to $X$. Let
$x^{\prime}\in X$ be the last vertex of $P$. If $x\neq x^{\prime}$, then
$\lambda_{D}(x,x^{\prime})\geq\lambda_{D[X]}(x,x^{\prime})+1=k+1$, a
contradiction. So $x=x^{\prime}$ and thus $y\in R^{-}(x)$. Hence,
$R^{+}(x)\subseteq R^{-}(x)$ and similarly $R^{-}(x)\subseteq R^{+}(x)$. So
$R^{+}(x)=R^{-}(x)$ and we set $R(x)=R^{+}(x)$. Since $D$ is biconnected,
there exists a shortest path $P=x_{1}\dots x_{\ell}$ in the underlying graph
of $D\setminus x$ with $x_{1}\in X$ and $x_{\ell}\in R(x)$. If $\ell\geq 3$,
then $x_{\ell-1}\in V(D)\setminus(X\cup R(x))$. But then if
$x_{\ell-1}x_{\ell}\in A(D)$, then $x_{\ell-1}\in R^{-}(x)$ and if
$x_{\ell}x_{\ell-1}\in A(D)$, then $x_{\ell-1}\in R^{+}(x)$, and thus
$x_{\ell-1}\in R(x)$ in both cases, a contradiction. So $\ell=2$. But then,
either $x_{1}x_{2}\in A(D)$ and thus $\lambda_{D}(x_{1},x)=k+1$ or
$x_{2}x_{1}\in A(D)$ and thus $\lambda_{D}(x,x_{1})=k+1$, a contradiction in
both cases. This proves that $D$ is $(k+1)$-vertex-dicritical.

Let $x,y\in V(D)$ and assume for contradiction that $\lambda_{D}(x,y)\leq
k-1$. Then, by Menger Theorem 3.1, $D$ has a dicut $(X,\overline{X})$ of size
at most $k-1$ with $x\in X$ and $y\in\overline{X}$. Since $D$ is $k$-vertex-
dicritical, we have that $\operatorname{\overrightarrow{\chi}}(X)\leq k$ and
$\operatorname{\overrightarrow{\chi}}(\overline{X})\leq k$ and thus, by
Corollary 3.4, $\operatorname{\overrightarrow{\chi}}(D)\leq k$, a
contradiction. Hence $\lambda(x,y)=k$ for every pair of distinct vertices
$x,\,y$.

Let $xy\in A(D)$, and let $H=D-xy$. Since $\lambda_{D}(x,y)=k$,
$\lambda_{H}(x,y)=k-1$ and, as above,
$\operatorname{\overrightarrow{\chi}}(H)\leq k$. So $D$ is $k+1$-dicritical.

Finally, by Theorem 3.2, $D$ is Eulerian. ∎

As a direct consequence, we get the characterization of $1$-extremal digraphs.

######  Theorem 4.2.

A digraph is $1$-extremal if and only if it is a directed cycle.

###### Proof.

It is clear that all directed cycles are $1$-extremal. Conversely, if $D$ is a
$1$-extremal digraph, then it is $2$-dicritical by Lemma 4.1 and is thus a
directed cycle. ∎

Since a $k$-extremal digraph $D$ is $k+1$-dicritical, for any arc $uv$ there
exists a $k$-dicolouring of $D-uv$, and if we put back the arc, then some
monochromatic cycles must go through $uv$, and thus the $k$-dicolouring of
$D-uv$ has some monochromatic $vu$-dipath. In the case of a digon, we can say
more.

######  Lemma 4.3.

Let $k\geq 1$. If $D$ is $k$-extremal and $[u,v]\subseteq A(D)$, then for
every $k$-dicolouring of $D-[u,v]$, there is no monochromatic $uv$-dipath nor
monochromatic $vu$-dipath.

Thus in any $k$-extremal digraph $D$ with a digon $[u,v]$, there exists an
assignment of $k$ colours to the vertices such that the only monochromatic
directed cycle is the digon $[u,v]$.

###### Proof.

Consider a digon $[u,v]$ in a $k$-extremal digraph $D$. By Lemma 4.1, $D$ is
$k+1$-dicritical. Eulerian, and $\lambda(u,v)=k$. Let $\varphi$ be a
$k$-dicoulouring of $D-[u,v]$ and let $(X_{1},X_{2})$ be a $uv$-dicut of size
$k$. We now apply Lemma 3.3 to $D$ and $\phi_{1}=\phi|_{X_{1}}$ and
$\phi_{2}=\phi|_{X_{2}}$. Note that since $D$ is Eulerian, we are in the
situation where $X_{1}$ and $X_{2}$ play the same role, so without loss of
generality we may assume that $X_{1}$ is the side of the cut such where only
one colour class contains vertices incident to arcs in the cut (the first item
in the statement of the lemma). Moreover, there exists exactly one arc in each
direction between this colour class and every colour class of $\phi_{2}$.
Since the digon $[u,v]$ is across the cut, and since $u$ and $v$ must get the
same colour in $\phi$ (for $D$ is not $k$-dicolourable), the arcs $uv$ and
$vu$ are the only monochromatic arcs across the cut, so that in $\phi$ there
exists no monochromatic $uv$-dipath nor monochromatic $vu$-dipath except for
the arcs of the digon.

∎

Along the proof, we will sometimes need to contract one side of a minimum
dicut of a $k$-extremal digraph and apply induction on the obtained digraph.
For this to work properly, we need to ensure that the obtained digraph is also
$k$-extremal. This done in Lemma 4.4. We also need to ensure that the dicut
does not isolate any vertex so that the obtained digraph is strictly smaller
than the original digraph. To prove that we can always find such a dicut, we
use a method derived from [29] (see also Section 3 of [1] for its use in
proving Brooks’ theorem for digraphs) in the case where $k\geq 4$, see Lemma
4.5, and a method derived from [22] (see also Section 5 of [1] for its use in
proving Brooks’ theorem for digraphs) in the case where $k=3$, see Lemma 4.6.

######  Lemma 4.4.

Let $k\geq 1$. Let $D$ be a $k$-extremal digraph and let $(A,\overline{A})$ be
a minimum dicut of $D$. Then $D/A$ or $D/\overline{A}$ is $k$-extremal.

###### Proof.

Set $H=D/A$ and let $a$ be the vertex into which $A$ is contracted in $H$.
Since $D$ is strong, so is $H$.

Let us first prove that $\lambda(H)\leq k$. By Lemma 4.1, $D$ is Eulerian, and
thus $d^{+}(a)=k$ and $d^{-}(a)=k$. Let $u,v\in H$, and let us prove that
$\lambda(u,v)\leq k$. Since $d^{+}(a),d^{-}(a)\leq k$, the result holds if
$a\in\\{u,v\\}$. Let $(B,\overline{B})$ be a minimum $uv$-dicut in $D$.

$|\partial_{D}|$ is submodular, i.e. it satisfies that $\forall S,T\subseteq
V(D),\partial_{D}(S)+\partial_{D}(T)\geq\partial_{D}(S\cup
T)+\partial_{D}(S\cap T)$.

By Lemma 4.1, the local arc-connectivity of any pair of vertices of $D$ is
$k$, so, given $X\subset V(D)$ distinct from $\emptyset$ and $V(D)$, we have
$\partial_{D}(X)\geq 2k$ and equality holds if and only if
$|\partial_{D}^{+}(X)|=|\partial_{D}^{+}(\overline{X})|=k$.

By submodularity of $|\partial_{D}|$,
$4k=|\partial_{D}(A)|+|\partial_{D}(B)|\geq|\partial_{D}(A\cap
B)|+|\partial_{D}(A\cup B)|$. Moreover, since $v\in\overline{B}$, $A\cap
B\neq\emptyset$ and $A\cup B\neq V(D)$, and it is clear that $A\cap B\neq
V(D)$ and $A\cup B\neq\emptyset$. Thus $|\partial_{D}(A\cup B)|=2k$, which
implies that $|\partial_{H}^{+}(B\setminus A\cup\\{a\\})|\leq k$, i.e.
$(B\setminus A\cup\\{a\\},\overline{B}\setminus A)$ is a $uv$-dicut of $H$ of
size at most $k$.

Let us now show that $H$ is biconnected. For every $x\in\overline{A}$,
$H\setminus x=(D\setminus x)/A$ is connected because $D\setminus x$ is
connected. So it suffices to show that $H\setminus a$ is connected. Let $X,Y$
be two connected components of $H\setminus a$. As $H$ is strong, there must be
at least one arc from $a$ to $X$. But as $(A,\overline{A})$ is a minimum dicut
of $D$, $a$ has outdegree $k$ in $H$, and thus there are at most $k-1$ arcs
from $a$ to $Y$. Thus $(\overline{Y},Y)$ is a dicut of $D$ of size at most
$k-1$, a contradiction. So $H$ is biconnected.

As $D$ is Eulerian, $(\overline{A},A)$ is also a minimum dicut of $D$. Thus
$D/\overline{A}$ is both strong and biconnected, and
$\lambda(D/\overline{A})=k$.

We now show that either $\operatorname{\overrightarrow{\chi}}(H)\geq k+1$ or
$\operatorname{\overrightarrow{\chi}}(D/\overline{A})\geq k+1$. Let
$\varphi_{A}$ be a $k$-dicolouring of $D[A]$ and $\varphi_{\overline{A}}$ a
$k$-dicolouring of $D[\overline{A}]$. By Lemma 3.3, we may assume without loss
of generality that every vertex $N(\overline{A})\cap A$ are coloured $1$. ,
and that every colour is used by vertices in $N(A)\cap\overline{A}$.

Let us prove that $\operatorname{\overrightarrow{\chi}}(H)\geq k+1$. Suppose
for contradiction that $H$ admits a proper $k$-dicolouring $\varphi_{H}$,
chosen, up to permuting colours, so that $\varphi_{H}(a)=1$. Consider
$\varphi:V(D)\to[1,k]$ such that $\varphi(x)=\varphi_{A}(x)$ if $x\in A$ and
$\varphi(x)=\varphi_{H}(x)$ if $x\in\overline{A}$. Since $N(\overline{A})\cap
A$ are coloured $1$ with respect to $\varphi_{A}$, it is easy to see that
$\varphi$ is a $k$-dicolouring of $D$, a contradiction. ∎

Recall that given a vertex $x$, $d_{max}(x)=max(d^{+}(x),d^{-}(x))$ and
$\Delta_{max}(D)=max_{x\in V(D)}d_{max}(x)$.

######  Lemma 4.5.

Let $k\geq 4$. If all minimum dicuts of a $k$-extremal digraph $D$ isolate a
vertex, then $D=\overleftrightarrow{K}_{k+1}$.

###### Proof.

Let $D$ be a $k$-extremal digraph in which every minimum dicut isolates a
vertex. If $\Delta_{max}(D)=k+1$, then $D=\overleftrightarrow{K}_{k+1}$ by
Theorem 1.3. Otherwise, since for every vertex of $x\in V(D)$, $d_{max}(x)\geq
k$, $D$ has a vertex with outdegree strictly greater than $k$ or a vertex with
indegree strictly greater than $k$.

If there are two distinct vertices $u$ and $v$ with $d_{max}(u)\geq k+1$ and
$d_{max}(v)\geq k+1$, then a minimum $uv$-dicut does not isolate $u$ nor $v$
(because $\lambda(u,v)=k$ and $D$ is Eulerian by Lemma 4.1 and thus, if
$(U,V)$ is a minimum $uv$-dicut, then it has size $k$, and since $D$ is
Eulerian, $(V,U)$ also has size $k$). So there is a vertex $u$ with
$d_{max}(u)\geq k+1$, and for every $x\in V(D)\setminus u$,
$d^{+}(x)=d^{-}(x)=k$.

Let $M\subseteq V(D)$ be a maximal set of vertices such that $u\in M$ and
$D[M]$ is acyclic. Then every vertex of $V(D)\setminus M$ has outdegree and
indegree at most $k-1$ in $V(D)\setminus M$, i.e.
$\Delta_{max}(D[V(D)\setminus M])\leq k-1$. As
$\operatorname{\overrightarrow{\chi}}(D[M])=1$ and
$\operatorname{\overrightarrow{\chi}}(D)=k+1$, we have that
$\operatorname{\overrightarrow{\chi}}(D[V(D)\setminus M])\geq
k\geq\Delta_{max}(D[V(D)\setminus M])+1$. By Theorem 1.3 applied on
$D[V(D)\setminus M]$, there exists $K\subseteq V(D)\setminus M$ such that
$D[K]=\overleftrightarrow{K_{k}}$. As every vertex of $K$ has in- and
outdegree exactly $k$ in $D$ and $k-1$ in $D[K]$,
$\partial^{+}(K)=\partial^{-}(K)=k$. Thus $(K,\overline{K})$ is a minimum
dicut and thus $V(D)\setminus K=\\{u\\}$ by hypothesis, a contradiction to the
fact that $d_{max}(u)\geq k+1$. ∎

######  Lemma 4.6.

If all minimum dicuts of a $3$-extremal digraph $D$ isolate a vertex, then
$D=\overleftrightarrow{W}_{2\ell+1}$ for some $\ell\geq 1$ or $D$ is a
directed Hajós join or a bidirected Hajós join of two digraphs.

###### Proof.

Let $D$ be a $3$-extremal digraph in which every minimum dicut isolates a
vertex, and assume for contradiction that $D$ is not a symmetric odd wheel nor
a directed Hajós join. Similarly to the proof of Lemma 4.5, we can prove that
there is a unique vertex $u$ with $d^{+}(u)=d^{-}(u)\geq 4$ and for every
$v\in V(D)\setminus u$, $d^{+}(v)=d^{-}(v)=3$.

Let $P=(X,Y)$ be a partition of $V(D)$. We say that $P$ is a special partition
if $u\in X$, $D[X]$ is acyclic and $X$ has maximum size among all sets
$X^{\prime}$ such that $u\in X^{\prime}$ and $D[X^{\prime}]$ is acyclic. Note
that if $P=(X,Y)$ is a special partition, then every vertex of $Y$ has at
least one inneighbour and one outneighbour in $X$, and thus has in- and
outdegree at most $2$ in $D[Y]$.

An obstruction of $P$ is a connected component of $D[Y]$ isomorphic to a
symmetric odd cycle. Since obstructions are $2$-regular, a connected component
of $D[Y]$ contains an obstruction if and only if it isomorphic to an
obstruction. Note also that every special partition has at least one
obstruction, for otherwise, by Theorem 1.3,
$\operatorname{\overrightarrow{\chi}}(D[Y])\leq 2$ and thus
$\operatorname{\overrightarrow{\chi}}(D)\leq 3$, a contradiction.

$P$ is said to be a super-special partition if it is special and it minimizes
the number of obstructions among all special partitions.

We call the following operation switching $x$ and $y$.

######  Claim 4.6.1.

Let $P=(X,Y)$ be a super-special partition. Let $y$ be a vertex in an
obstruction of $P$, and $x\in X\setminus\\{u\\}$ be a neighbour of $y$. Then
$P^{\prime}=(X\cup\\{y\\}\setminus\\{x\\},Y\cup\\{x\\}\setminus\\{y\\})$ is a
super-special partition, and $x$ is in an obstruction of $P^{\prime}$.

Proof of Claim : Suppose without loss of generality that $xy\in A(D)$. Let
$Z\subseteq Y$ be the vertex set of the obstruction containing $y$. As
$d^{-}(y)=3$ and $y$ has $2$ inneighbours in $Z$, $y$ has no inneighbour in
$X\setminus\\{x\\}$. Thus $D[X\cup\\{y\\}\setminus\\{x\\}]$ is acyclic. As
$x\neq u$, $P^{\prime}$ is special. Since removing any vertex of a symmetric
odd cycle yields a digraph that is not a symmetric odd cycle,
$D[Z\setminus\\{y\\}]$ is not a symmetric odd cycle. Thus $x$ is in an
obstruction of $P^{\prime}$ and $P^{\prime}$ is super-special. $\square$

The switching operation is particularly useful thanks to the following claim:

######  Claim 4.6.2.

Let $P=(X,Y)$ be a super-special partition, and $Z$ the vertex set of an
obstruction of $P$. Vertices in $X\setminus u$ have at most one neighbour in
$Z$.

Proof of Claim : Let $Z=\\{v_{1},\dots,v_{s}\\}$ and $v_{i}$ and $v_{i+1}$ are
linked by a digon for $i=1,\dots,s$ (subscript are taken modulo $s$). Suppose
for contradiction that there is $x\in X\setminus\\{u\\}$ such that $x$ is a
neighbour of $v_{i}$ and $v_{j}$ for some $i\neq j$. By claim 4.6.1, we can
switch $x$ and $v_{i}$ to obtain the super special partition
$P^{\prime}=(X\cup\\{v_{i}\\}\setminus\\{x\\},Y\cup\\{x\\}\setminus\\{v_{i}\\})$.
Since $x$ is a neighbour of $v_{j}$, the obstruction of $P^{\prime}$
containing $x$ is $D[Z\cup\\{x\\}\setminus\\{a\\}]$, i.e.
$D[Z\cup\\{x\\}\setminus\\{a\\}]$ is a symmetric odd cycle. Hence, $x$ is
linked by a digon to $v_{i-1}$ and $v_{i+1}$. Now, by switching $x$ and
$v_{i+1}$ in $P$, we get that $x$ is also linked by a digon to $v_{i+2}$ and
thus is linked by a digon to every vertex of $Z$. This implies that $s=3$, and
thus the dicut $(V(Z),V(D)\setminus V(Z))$ has size $3$, so it is a minimum
dicut that does not isolate a vertex, a contradiction. $\square$

Let $P_{1}=(X_{1},Y_{1})$ be a super-special partition of $D$ and let $Z_{1}$
an obstruction of $P_{1}$. If no vertex of $Z_{1}$ has a neighbour in
$X_{1}\setminus\\{u\\}$, then $D[Z\cup\\{u\\}]$ is a symmetric odd wheel and
we are done. So there exist $x_{1}\in X_{1}\setminus\\{u\\}$ and $y_{1}\in
Z_{1}$ such that $x_{1}$ and $y_{1}$ are adjacent. Set
$Q_{1}=Z_{1}\setminus\\{y_{1}\\}$.

By claim 4.6.1, $P_{2}=(X_{2},Y_{2})$ with
$X_{2}=X_{1}\cup\\{y_{1}\\}\setminus\\{x_{1}\\}$ and
$Y_{2}=Y_{1}\cup\\{x_{1}\\}\setminus\\{y_{1}\\}$ is a super-special partition
and $x_{1}$ is in an obstruction $Z_{2}$ of $P_{2}$. Let
$Q_{2}=Z_{2}\setminus\\{x_{1}\\}$, so $Q_{2}$ is a symmetric path and is a
connected component of $D[Y_{1}]$. Observe that no vertex of $Q_{2}$ is
adjacent with $y_{1}$. If $y_{1}$ is the only vertex in
$X_{2}\setminus\\{u\\}$ with a neighbour in $V(Z_{2})$, then either $x_{1}$
and $y_{1}$ are linked by a digon and $D$ is a bidirected Hajós join (by Lemma
5.7, because deleting $u$ and $[x_{1},y_{1}]$ separates $Z_{2}$ from the rest
of the digraph), or $D$ is a directed Hajós join (by Lemma 5.4, because
deleting $u$ and the arc linking $x_{1}$ and $y_{1}$ separates $Z_{2}$ from
the rest of the digraph). A contradiction in both cases. Hence, there is
$x_{2}\in X_{2}\setminus\\{u,y_{1}\\}$ such that $x_{2}$ has a neighbour
$y_{2}\in V(Z_{2})$.

Let $P_{3}=(X_{3},Y_{3})$ where
$X_{3}=X_{2}\cup\\{y_{2}\\}\setminus\\{x_{2}\\}$ and
$Y_{3}=Y_{2}\cup\\{x_{2}\\}\setminus\\{y_{2}\\}$. By claim 4.6.1, $P_{3}$ is a
super-special partition and $x_{2}$ is in an obstruction $Z_{3}$ of $P_{3}$.
Note that, claim 4.6.2, $x_{2}$ has at most one neighbour in $Z_{1}$ and in
$Z_{2}$, but it has two neighbours in $Z_{3}$, this implies that $Z_{3}$ is
disjoint from $Z_{1}$ and $Z_{2}$. As previously, if $y_{2}$ is the only
vertex in $X_{3}\setminus u$ with a neighbour in $Z_{3}$, then $D$ is a
directed Hajós join or a bidirected Hajós join, a contradiction. So there
exists $x_{3}\in X_{3}\setminus\\{u,y_{1},y_{2}\\}$ such that $x_{3}$ has a
neighbour $y_{3}\in V(Z_{3})$.

This process can be continued and never stop, a contradiction.

∎

##  5 Directed Hajós joins and Hajós bijoins - A First Decomposition Theorem

Our main theorem presented in the introduction (Theorem 1.8) is a structure
theorem for the class of $k$-extremal digraphs, in the sense that it is an "if
and only if". The goal of this section is to prove an intermediate result that
is a decomposition theorem for this class (an "only if" theorem). It involves
the notion of Hajós bijoin described just after the statement.

######  Theorem 5.1.

Let $k\geq 3$. If $D$ is $k$-extremal, then:

  * •

either $D=\overleftrightarrow{K}_{k+1}$

  * •

or $D$ is a symmetric odd wheel (only in the case $k=3$),

  * •

or $D$ is a directed Hajós join of two $k$-extremal digraphs,

  * •

or $D$ is a Hajós bijoin of two $k$ extremal-digraphs.

######  Definition 5.2 (Hajós bijoin and degenerated Hajós bijoin).

Let $D_{1}$ and $D_{2}$ be two digraphs. Let $ta_{1},a_{1}w\in A(D_{1})$
($t=w$ is possible) and $t$ and $w$ are in the same connected component of
$D_{1}\setminus a_{1}$. Let $va_{2},a_{2}u\in A(D_{2})$ ($u=v$ is possible)
and $u$ and $v$ are in the same connected component of $D_{2}\setminus a_{2}$.
The Hajós bijoin of $D_{1}$ and $D_{2}$ with respect to
$\big{(}(t,a_{1},w),(v,a_{2},u)\big{)}$ is the digraph $D$ obtained from the
disjoint union of $D_{1}-\\{ta_{1},a_{1}w\\}$ and $D_{2}-\\{va_{2},a_{2}u\\}$
by identifying $a_{1}$ and $a_{2}$ into a new vertex $a$, and adding the arcs
$tu$ and $vw$.
If $t=w$ and $u\neq v$ (or $u=v$ and $t\neq w$), we say it is a degenerated
Hajós bijoin.
If $t=w$ and $u=v$, then it is the bidirected Hajós join of $D_{1}$ and
$D_{2}$ with respect to $([t,a_{1}],[u,a_{2}])$. See Figure 3.

$t$$w$$a$$u$$v$$D$$a_{1}$$t$$w$$D_{1}$$a_{2}$$u$$v$$D_{2}$ Figure 3: $D$ is
the Hajós bijoin of $D_{1}$ and $D_{2}$ with respect to
$(t,a_{1},w),(u,a_{2},v)$.

###  5.1 Properties of directed Hajós joins

For the definition of directed Hajós join, see Definition 1.5. We first prove
an essential result about $k$-extremal digraphs and directed Hajós joins

######  Lemma 5.3.

Let $k\geq 1$. Let $D$ be the directed Hajós join of two digraphs $D_{1}$ and
$D_{2}$. Then $D$ is $k$-extremal if and only if both $D_{1}$ and $D_{2}$ are.

###### Proof.

Suppose $D$ is a directed Hajós join of two digraphs $D_{1}$ and $D_{2}$ with
respect to $(uv_{1},v_{2}w)$, i.e. there is $uv_{1}\in A(D_{1})$ and
$v_{2}u\in A(D_{2})$ such that $D$ is obtained from disjoint copies of
$D_{1}-uv_{1}$ and $D_{2}-v_{2}w$ by identifying the vertices $v_{1}$ and
$v_{2}$ to a new vertex $v$ and adding the edge $uw$.

######  Claim 5.3.1 (Theorem 2 in [3]).

$D$ is $k+1$-dicritical if and only if both $D_{1}$ and $D_{2}$ are.

Let us first suppose that $D_{1}$ and $D_{2}$ are $k$-extremal. By Claim
5.3.1, $D$ is $k+1$-dicritical, so it is also biconnected and strong. Since
the maximum local arc-connectivity of a digraph equal the maximum maximum
local arc-connectivity of its blocks, we have that
$\lambda(D-\\{uw\\}+\\{uv_{1},v_{2}w\\})=\max(\lambda(D_{1}),\lambda(D_{2}))=k$,
and by Lemma 3.5, $\lambda(D)\leq\lambda(D-\\{uw\\}+\\{uv_{1},v_{2}w\\}=k$.
Thus $k+1=\operatorname{\overrightarrow{\chi}}(D)\leq\lambda(D)+1=k+1$, so
$\lambda(D)=k$ and $D$ is $k$-extremal.

Suppose now that $D$ is $k$-extremal. By claim 5.3.1, both $D_{1}$ and $D_{2}$
are $(k+1)$-dicritical and thus are also strong and biconnected. Since $D$ is
strong, it has a $wv$-dipath, and this dipath uses only arcs in the copy of
$D_{2}-wv_{2}$. Let $P$ be such a dipath to which we add the arc $uw$ at the
beginning. Then $\lambda(D+uv-A(P))\leq\lambda(D)=k$, and since $D_{1}$ is a
subdigraph of $D+uv-A(P)$, we have that $\lambda(D_{1})\leq k$. Thus
$k+1=\operatorname{\overrightarrow{\chi}}(D_{1})\leq\lambda(D_{1})+1=k+1$, so
$\lambda(D)=k$ and $D_{1}$ is $k$-extremal. Similarly, $D_{2}$ is
$k$-extremal. ∎

If $D$ is a directed Hajós join of two digraphs, then there exists an arc
$uw$, such that $D-uw$ has a cutvertex. The following lemma asserts that if
$D$ is $k$-extremal, then the converse holds. This is sometimes useful to
prove that $D$ is a directed Hajós join.

######  Lemma 5.4.

Let $k\geq 1$. Let $D$ be a $k$-extremal digraph with an arc $uw\in A(D)$,
such that $D-uw$ has a cutvertex $v$. Then $D$ is a directed Hajós join of two
digraphs $D_{1}$ and $D_{2}$ with respect to $(uv,vw)$.

###### Proof.

Let $v$ be the cutvertex of $D-uw$. Since $D$ is biconnected, $D-uw$ has
exactly two blocks $D_{1}$ and $D_{2}$ containing respectively $u$ and $w$.
Thus it is enough to prove that $uv\not\in A(D)$ and $vw\not\in A(D)$. We only
prove it for $uv$, the argument for $vw$ is identical. Assume by contradiction
$uv\in A(D)$. By Lemma 4.1, $D$ is $k+1$-dicritical, so $D_{i}$ has a
$k$-dicolouring $\varphi_{i}$ for $i=1,2$. Since $uv$ is an arc, there is no
monochromatic $vu$-dipath with respect to $\varphi_{1}$. Up to permuting
colours, we may assume that $\varphi_{2}(v)=\varphi_{1}(v)$. Let
$\varphi:V(D)\rightarrow[k]$ defined as follow: $\varphi(x)=\varphi_{1}(x)$ if
$x\in V(D_{1})$, and $\varphi(x)=\varphi_{2}(x)$ if $x\in V(D_{2})$. We claim
that $\varphi$ is a $k$-dicolouring of $D$. Indeed, by construction of
$\varphi$ there is no monochromatic dicycle included in $D_{1}$ or $D_{2}$,
and a dicycle intersecting both $D_{1}$ and $D_{2}$ contains a $vu$ dipath
included in $D_{1}$, and thus cannot be monochromatic. Thus $\varphi$ is a
$k$-dicolouring of $D$, a contradiction. ∎

###  5.2 Properties of Hajós bijoin

We start with the analogue of Lemma 5.3 for bijoins, but note that we have
only one direction here.

######  Lemma 5.5.

Let $k\geq 3$. Let $D$ be a Hajós bijoin of two digraphs $D_{1}$ and $D_{2}$.
If $D$ is $k$-extremal, then both $D_{1}$ and $D_{2}$ are $k$-extremal.

###### Proof.

Let $D$ be a $k$-extremal digraph, and $D$ is a Hajós bijoin of two digraphs
$D_{1}$ and $D_{2}$ with respect to $\big{(}(t,a_{1},w),(v,a_{2},u)\big{)}$,
i.e. there exists $tu,vw\in A(D)$ and $a\in V(D)$ such that
$D\setminus\\{a\\}-\\{tu,vw\\}$ has two connected components with vertex sets
$V^{\prime}_{1}$ and $V^{\prime}_{2}$ such that $D_{1}=D[V^{\prime}_{1}\cup
a]+\\{ta,aw\\}$, and $D_{2}=D[V^{\prime}_{2}\cup a]+\\{va,au\\}$ and $t$ and
$w$ are in the same connected component of $D_{1}\setminus a$ and $u$ and $v$
are in the same connected component of $D_{2}\setminus a$.

Let us first prove that $D_{1}$ is biconnected. Assume for contradiction that
$D_{1}$ has a cutvertex $x$. Observe that $\\{t,w,a_{1}\\}\setminus x$ are in
the same connected component of $D_{1}\setminus x$. Indeed, if $x=a$ it is by
hypothesis, and otherwise it is because $ta,aw\in A(D_{1})$. Hence,
$D\setminus x$ has a connected component disjoint from $\\{t,a,w\\}$, and thus
$x$ is a cutvertex of $D$, a contradiction.

As $D$ is Eulerian, so is $D_{1}$ by construction. And since an Eulerian
connected digraph is strong, $D_{1}$ is strong.

Let $x,y\in V(D_{1})$ and let us prove that $\lambda_{D_{1}}(x,y)\leq k$. Let
$(X,\overline{X})$ be a minimum $xy$-dicut in $D$, i.e. $x\in X$ and
$y\in\overline{X}$. Since $D$ is $k$-extremal, $(\overline{X},X)$ is a minimum
$yx$-dicut, and thus, up to permuting $y$ and $x$, we may assume without loss
of generality that $a\in\overline{X}$. Let $X_{D_{1}}=X\cap V(D_{1})$ and
consider the $xa$-dicut of $D$ $(X_{D_{1}},\overline{X}_{D_{1}})$. If $t\in
X$, then $\partial_{D_{1}}^{+}(X)=\partial_{D}^{+}(X)-tu+ta$, and otherwise
$\partial_{D_{1}}^{+}(X)=\partial_{D}^{+}(X)$. Hence
$|\partial_{D_{1}}^{+}(X)|=|\partial_{D}^{+}(X)|=k$, so
$\lambda_{D_{1}}(u,v)\leq k$ and thus $\lambda(D_{1})\leq k$.

Let us now prove that $\operatorname{\overrightarrow{\chi}}(D_{1})\geq k+1$.
Suppose $D_{1}$ admits a $k$-dicolouring $\varphi_{1}$. Let $\varphi_{2}$ be a
$k$-dicolouring of $D_{2}-\\{va,au\\}$ such that
$\varphi_{1}(a)=\varphi_{2}(a)$ and, if $\varphi_{1}(a)\neq\varphi_{1}(t)$,
such that $\varphi_{2}(u)\neq\varphi_{1}(t)$ (this can always be done because
$k\geq 3$). Consider $\varphi:V(D)\to[1,k]$ such that
$\varphi(x)=\varphi_{1}(x)$ if $x\in V(D_{1})\cup a$ and
$\varphi(x)=\varphi_{2}(x)$ if $x\in V(D_{2})$.

Since $\operatorname{\overrightarrow{\chi}}(D)=k+1$, $D$ has a monochromatic
directed cycle $C$ with respect to $\varphi$. By construction of $\varphi$,
$C$ goes through $tu$, or $vw$ or both. If $C$ goes through $tu$ but not $vw$,
then $C$ contains an $at$-dipath, which is not monochromatic since $ta\in
A(D_{1})$ and $\varphi_{1}$ is a $k$-dicolouring of $D_{1}$, a contradiction.
Similarly, we get a contradiction if $C$ goes through $vw$ but not $tu$. We
may thus assume that $C$ uses both $tu$ and $vw$. In particular, $C$ contains
an $uv$-dipath $P_{uv}$ included in $D_{2}$, and a $wt$-dipath $P_{wt}$
included in $D_{1}$. If $\varphi_{1}(a)=\varphi_{1}(t)$, then $P_{wt}$ plus
the arcs $ta$ and $aw$ form a monochromatic dicyle of $D_{1}$, a
contradiction. Thus $\varphi_{1}(a)\neq\varphi_{1}(t)$ and thus
$\varphi(t)\neq\varphi(u)$ by construction of $\varphi$, so $C$ is not
monochromatic, a contradiction. This finishes the proof that
$\operatorname{\overrightarrow{\chi}}(D_{1})\geq k+1$.

Now, since
$k+1\leq\operatorname{\overrightarrow{\chi}}(D_{1})\leq\lambda(D_{1})+1\leq
k+1$, we have
$\operatorname{\overrightarrow{\chi}}(D_{1})=\lambda(D_{1})+1=k+1$. Altogether
we get that $D_{1}$ is $k$-extremal. Similarly, $D_{2}$ is $k$-extremal. ∎

Note that the reciprocal of lemma 5.5 does not hold, observe for example that
the Hajós bijoin of two $\overleftrightarrow{K}_{k+1}$ is $k$-dicolourable and
is thus not $k$-extremal. See Figure 4.

atwuv Figure 4: A $4$-dicolouring of a bijoin of two
$\overleftrightarrow{K}_{4}$.

However, we can still prove the following holds:

######  Lemma 5.6.

Let $k\geq 3$. Let $D$ be a Hajós bijoin of two digraphs $D_{1}$ and $D_{2}$.
If, for $i=1,2$, $D_{i}$ is biconnected, strong, Eulerian and
$\lambda(D_{i})\leq k$, then $D$ is biconnected, strong, Eulerian and
$\lambda(D)\leq k$.

###### Proof.

Let, for $i=1,2$, $D_{i}$ be a biconnected, strong, Eulerian digraph with
$\lambda(D_{i})\leq k$. Let $D$ be a Hajós bijoin of $D_{1}$ and $D_{2}$ with
respect to $\big{(}(t,a_{1},w),(v,a_{2},u)\big{)}$, i.e. there exists
$tu,vw\in A(D)$ and $a\in V(D)$ such that $D\setminus\\{a\\}-\\{tu,vw\\}$ has
two connected components with vertex set $V^{\prime}_{1}$ and $V^{\prime}_{2}$
such that $D_{1}=D[V^{\prime}_{1}\cup a]+\\{ta,aw\\}$, and
$D_{2}=D[V^{\prime}_{2}\cup a]+\\{va,au\\}$ and $t$ and $w$ are in the same
connected component of $D_{1}\setminus a$ and $u$ and $v$ are in the same
connected component of $D_{2}\setminus a$. Set $V_{1}=V^{\prime}_{1}\cup a$
and $V_{2}=V^{\prime}_{2}\cup a$.

Let us first prove that $D$ is biconnected. Assume for contradiction that $D$
has a cutvertex $x$. Since for $i=1,2$ $D_{i}$ is biconnected,
$D[V^{\prime}_{i}]=D_{i}\setminus a$ is connected, and since moreover there is
an (actually two) arc between $D[V^{\prime}_{1}]$ and $D[V^{\prime}_{2}]$,
$D\setminus a$ is connected. Thus $x\neq a$. Assume without loss of generality
that $x\in V^{\prime}_{1}$ and let $C$ be the connected component of
$D\setminus x$ containing $a$. Then $V_{2}$ is included in $C$, and since
there is an arc between $u$ and $V_{2}$ and between $w$ and $V_{2}$, $u$ and
$w$ are also in $C$. Thus $a$, $u$ and $w$ are in the same connected component
of $D\setminus x$, which implies that $x$ is a cutvertex of $D_{1}$, a
contradiction.

As $D_{1}$ and $D_{2}$ are Eulerian, so is $D$ by construction. And since an
Eulerian biconnected digraph is strong, $D_{1}$ is strong.

Let $D^{\prime}=D-\\{tu,vw\\}+\\{ta,au,va,aw\\}$. As the blocks of
$D^{\prime}$ are $D_{1}$ and $D_{2}$, $\lambda(D^{\prime})\leq k$. Hence, by
applying twice Lemma 3.5, we get that $\lambda(D)\leq\lambda(D^{\prime})\leq
k$. ∎

The following lemma is an analogue of Lemma 5.4 in the case of degenerated
Hajós bijoins.

######  Lemma 5.7.

Let $k\geq 3$. Let $D$ be a $k$-extremal digraph. Suppose there exists $tu$
and $uw$ in $A(D)$, such that $D-\\{tu,uw\\}$ has a cutvertex. Then $D$ is a
directed Hajós join or a Hajós bijoin.

###### Proof.

Note that since $D$ is biconnected, $D-\\{tu,uw\\}$ is connected. Let $a$ be a
cut-vertex of $D-\\{tu,uw\\}$. Assume first that $t$ and $w$ are in two
distinct connected components of $D\setminus a-\\{tu,uw\\}$ and assume without
loss of generality that $u$ is not in the same connected component as $t$.
Then $D\setminus a-\\{tu\\}$ is disconnected, and thus $D$ is a directed Hajós
join by Lemma 5.4.

We may thus assume that $t$ and $w$ are in the same connected component of
$D\setminus a-\\{tu,uw\\}$. To prove that $D$ is a Hajós bijoin, it is enough
to prove that $ta,aw,ua,au\notin A(D)$. We will prove something a bit
stronger.

######  Claim 5.7.1.

Let $k\geq 3$. Let $D^{\prime}$ be a $k$-extremal digraph. Suppose there
exists $a,t,u,v,w\in V(D^{\prime})$ with $a\notin\\{t,u,v,w\\}$ and
$\\{t,u\\}\cap\\{v,w\\}=\emptyset$ (in other words, $t=u$ and $v=w$ are the
only possible equalities) such that $tu,vw\in A(D^{\prime})$, $a$ is a
cutvertex of $D^{\prime}-\\{tu,vw\\}$ and $D^{\prime}-\\{tu,vw\\}$ has two
blocks $D_{1}$ and $D_{2}$ with $t,w\in V(D_{1})$ and $u,v\in V(D_{2})$. Then
$ta,au,va,aw\notin A(D^{\prime})$.

Proof of Claim : Suppose that $ta\in A(D^{\prime})$. Let us first prove that
$D_{1}+aw$ is biconnected, strong, and $\lambda(D_{1}+aw)\leq k$.

Assume for contradiction that $D_{1}+aw$ has a cutvertex $x$. Observe that
$\\{t,w,a\\}\setminus x$ are in the same connected component of
$D_{1}+aw\setminus x$. Indeed, if $x=a$ it is by hypothesis, and otherwise it
is because $ta,aw\in A(D_{1})\cup\\{aw\\}$. Hence, $D^{\prime}\setminus x$ has
a connected component included in $D_{1}$ and disjoint from $\\{t,a,w\\}$, and
thus $x$ is a cutvertex of $D^{\prime}$, a contradiction.

Since for any two vertices $u,v$ of $D^{\prime}$,
$\lambda_{D^{\prime}}(u,v)=k$, we have that
$\lambda_{D^{\prime}+aw-\\{tu,vw\\}}(u,v)\geq k-2\geq 1$, and thus
$D^{\prime}+aw-\\{tu,vw\\}$ is strong. As $D_{1}+aw$ is a block of
$D^{\prime}+aw-\\{tu,vw\\}$, $D_{1}+aw$ is strong.

Let $P_{av}$ be an $av$-dipath in $D_{2}$, which exists for
$\lambda_{D^{\prime}-\\{tu,vw\\}}(a,v)\geq\lambda_{D^{\prime}}(a,v)-2\geq
k-2\geq 1$. By Lemma 3.5,
$\lambda(D^{\prime}+aw-A(P_{av})-vw)\leq\lambda(D^{\prime})=k$, and since
$D_{1}+aw$ is a subgraph of $D^{\prime}+aw-A(P_{av})-vw$, we have
$\lambda(D_{1}+aw)\leq k$.

Hence, $D_{1}+aw$ is biconnected, strong, and $\lambda(D_{1}+aw)\leq k$. Yet
$D_{1}+aw$ is not Eulerian, for $D^{\prime}$ is Eulerian, and the indegree of
$t$ does not change in $D_{1}$ while its outdegree decreases by $1$. Thus, by
Lemma 4.1, $D_{1}+aw$ is not $k$-extremal, hence
$\operatorname{\overrightarrow{\chi}}(D_{1}+aw)\leq k$. Let $\varphi_{2}$ be a
$k$-dicolouring of $D_{2}$. Let $\varphi_{1}$ be a $k$-dicolouring of
$D_{1}+aw$ chosen so that

  * •

$\varphi_{1}(a)=\varphi_{2}(a)$ and,

  * •

if $\varphi_{1}(a)\neq\varphi_{1}(t)$, then $\varphi_{1}(t)\neq\varphi_{2}(u)$
(which is always possible up to permuting colours, since $k\geq 3$).

Consider $\varphi:V(D^{\prime})\rightarrow[k]$ such that

$\varphi(y)=\left\\{\begin{array}[]{ll}\varphi_{1}(y)&\text{ if }y\in
V(D_{1})\\\ \varphi_{2}(y)&\text{ if }y\in V(D_{2})\end{array}\right.$

Since $\operatorname{\overrightarrow{\chi}}(D^{\prime})=k+1$, $\varphi$
contains a monochromatic dicycle $C$. Since $\varphi_{1}$ and $\varphi_{2}$
are $k$-dicolourings of respectively $D_{1}+aw$ and $D_{2}$, $C$ intersects
both $V(D_{1})\setminus a$ and $V(D_{2})\setminus a$.
If $C$ contains $tu$ but not $vw$, then $C$ goes through $a$, and there is a
monochromatic $at$-dipath in $D_{1}+aw$ which, together with the arc $ta$,
forms a monochromatic dicycle with respect to $\varphi_{1}$, a contradiction
to the fact that $\varphi_{1}$ is a dicolouring of $D_{1}+aw$.
If $C$ contains $vw$ but not $tu$, then $C$ goes through $a$, and there is a
monochromatic $wa$-dipath in $D_{1}+wa$ which, together with the arc $aw$,
forms a monochromatic dicycle with respect to $\varphi_{1}$, a contradiction
with the fact that $\varphi_{1}$ is a dicolouring of $D_{1}+aw$.
If $C$ contains both $tu$ and $vw$, then there is a monochromatic $wt$-dipath
in $D_{1}$ with respect to $\varphi$. Since $ta,aw\in A(D_{1}+aw)$ and
$\varphi_{1}$ is a $k$-dicolouring of $D_{1}+aw$, this implies that
$\varphi_{1}(a)\neq\varphi(t)$. But then $\varphi(t)\neq\varphi(u)$ by the
choice of $\varphi_{1}$ and $\varphi$, a contradiction.

Hence, $\varphi$ has no monochromatic dicycle, a contradiction. Thus we have
proven that $ta\notin A(D^{\prime})$. By symmetry, we have that
$ta,au,va,aw\notin A(D^{\prime})$. $\square$

Applying this claim with $u=v$, this proves $ta,au,ua,aw\notin A(D)$ and thus
that $D$ is a Hajós bijoin.

∎

###  5.3 Proof of Theorem 5.1

Let $k\geq 3$. We prove the theorem by induction on the number of vertices.
Let $D$ be $k$-extremal, and assume by contradiction that $D$ is neither a
symmetric complete graph, a symmetric odd wheel, a directed Hajós join, nor a
Hajós bijoin.

Given a digraph $D$, a flower of $D$ is an induced subdigraph $F$ of $D$
isomorphic to a symmetric path $P$ with an even number of vertices plus a
vertex $x$ linked to each vertex of $P$ by a digon, and such that internal
vertices of $P$ has no neighbour outside $F$, while other (that is $x$ and the
two extremities of $P$) have exactly one inneighbour and one outneighbour
outside $F$. The vertex $x$ is called the center of $F$.

######  Claim 5.7.2.

$D$ has a minimum dicut $(X,\overline{X})$ such that either $k\geq 4$ and
$D[\overline{X}]=\overleftrightarrow{K}_{k}$, or $k=3$ and $D[\overline{X}]$
is a flower of $D$. Moreover, if $D[\overline{X}]=\overleftrightarrow{K}_{k}$,
then each vertex of $\overline{X}$ has exactly one inneighbour and one
outneighbour in $X$.

Proof of Claim : By Lemma 4.5 and Lemma 4.6, $D$ has a minimum dicut
$(A,\overline{A})$ such that $|A|>1$ and $|\overline{A}|>1$. By Lemma 4.4, up
to permuting $A$ and $\overline{A}$, we may assume that $D/A$ is $k$-extremal
and thus by induction is either a symmetric complete graphs on $k+1$ vertices,
a symmetric complete wheel, a Hajós bijoin of two $k$-extremal digraphs or a
directed Hajós join of two $k$-extremal digraphs.

Let $a$ be the vertex into which $A$ is contracted in $D/A$. Observe that,
since $(A,\overline{A})$ is a minimum dicut and $D$ is Eulerian, $a$ has
indegree an outdegree $k$ in $D/A$.

Assume first that there exist two $k$-extremal digraphs $D_{1}$ and $D_{2}$
such that $D/A$ is either a Hajós bijoin of $D_{1}$ and $D_{2}$ with respect
to $\big{(}(t,b_{1},w),(v,b_{2},u)\big{)}$ or a directed Hajós join of $D_{1}$
and $D_{2}$ with respect to $(ub_{1},b_{2}w)$, and let $b$ the vertex into
which $b_{1}$ and $b_{2}$ are identified in $D$. Then, as $b_{1}$ and $b_{2}$
both have outdegree at least $k$ in respectively $D_{1}$ and $D_{2}$, $b$ has
outdegree at least $2k-2>k$ in $k$, and thus $b\neq a$. We may thus assume
that $a$ is in $D_{1}\setminus a$ or in $D_{2}\setminus a$. Now, when one un-
contracts the vertex $a$ to get the original digraph $D$, it is clear that the
structure of the directed Hajós join or Hajós bijoin is preserved, i.e. $D$ is
a directed Hajós join or a Hajós bijoin, a contradiction.

Hence, we may assume that $D/A$ is a symmetric complete graph or a symmetric
odd wheel in which $a$ is a vertex of outdegree $k$. Hence, $D[\overline{A}]$
is either a $\overleftrightarrow{K}_{k}$, or a symmetric path $P$ with an even
number of vertices plus a vertex $x$ linked via a digon to each vertex of $P$.

Assume first that $D[\overline{A}]=\overleftrightarrow{K}_{k}$. Then each
vertex of $\overline{A}$ has at least one inneighbour and one outneighbour in
$A$ (because they linked to $a$ via a digon in $D/A$), and since
$(A,\overline{A})$ is a minimum dicut, it has exactly one of each. Assume now
that we are in the case where $D/A$ is a symmetric odd wheel, and thus
$D[\overline{A}]$ is a symmetric path $P$ with an even number of vertices plus
a vertex $x$ linked via a digon to each vertex of $P$. Observe that $x$ and
each extremity of $P$ has at least one inneighbour and one outneighbour in $A$
(because they are linked via a digon to $a$ in $D/A$). Hence, since
$(A,\overline{A})$ is a minimum dicut, $D[\overline{A}]$ is a flower.

Hence, by taking $X=A$, we get the desired properties.

$\square$

We distinguish between two cases depending on whether or not there is a vertex
of $\overline{X}$ that has two distinct in- and out-neighbour in $X$.

Case 1: There exist $v\in\overline{X}$ and $u,w\in X$ such that $uv,vw\in
A(D)$ and $u\neq w$

Let $D^{\prime}=D-\\{uv,vw\\}+\\{uw\\}$. Due to Lemma 3.5,
$\lambda(D^{\prime})\leq\lambda(D)=k$. Let us now show that
$\operatorname{\overrightarrow{\chi}}(D^{\prime})\geq k+1$. Suppose for
contradiction that $D^{\prime}$ admits a $k$-dicolouring $\varphi$. As
$\operatorname{\overrightarrow{\chi}}(D)=k+1$, $\varphi$ is not a
$k$-dicolouring of $D=D^{\prime}+\\{uv,vw\\}-\\{uw\\}$, and thus there is a
monochromatic dicycle $C$ in $D^{\prime}+\\{uv,vw\\}-\\{uw\\}$ containing $uv$
or $vw$ or both. By claim 5.7.2, $v$ is linked via a digon to all its
neighbours except for $u$ and $w$, so $C$ contains both $uv$ and $vw$. By
replacing the arcs $uv$ and $vw$ by $uw$ in $C$, we get a monochromatic
dicycle in $D^{\prime}$, a contradiction. Thus
$k+1\leq\operatorname{\overrightarrow{\chi}}(D^{\prime})\leq\lambda(D^{\prime})+1\leq
k+1$ and hence
$\operatorname{\overrightarrow{\chi}}(D^{\prime})=\lambda(D^{\prime})+1=k+1$.

Since there are $k$ arc-disjoint dipaths between any pair of vertices in $D$,
there are at least $k-2\geq 1$ arc-disjoint dipaths between any pair of
vertices in $D^{\prime}$, thus $D^{\prime}$ is strong. Since
$|\partial_{D^{\prime}}^{+}(X)|=k-1$, $D^{\prime}$ is not $k$-extremal by
Lemma 4.1. Thus $D^{\prime}$ is not biconnected.

Let $a$ be a cutvertex of $D^{\prime}$. Since $uw\in A(D^{\prime})$, $u$ and
$w$ are together in a block $B_{1}$ of $D^{\prime}$. Since $D[\overline{X}]$
is either $\overleftrightarrow{K}_{k}$ or a flower of $D$, $\overline{X}$ is
included in a block $B_{2}$ of $D^{\prime}$. If $D^{\prime}$ has a block
distinct from $B_{1}$ and $B_{2}$, then $a$ is a cutvertex of $D$, a
contradiction. Thus $B_{1}$ and $B_{2}$ are distinct and are the only blocks
of $D^{\prime}$. Now, $a$ is a cutvertex of $D-\\{uv,vw\\}$, and thus, by
Lemma 5.7, $D$ is a Hajós bijoin or a directed Hajós join, a contradiction.

Case 2: There are only digons between $X$ and $\overline{X}$

Assume $D[X]$ is not strong and let $C_{t}$ be a terminal component of $D[X]$.
We have $\partial^{+}(C_{t})\subseteq\overline{X}$ and
$|\partial^{+}(C_{t})|\geq k$, so the digons linking $X$ and $\overline{X}$
are all incident with some vertex of $C_{t}$. Thus $D$ is not strong, a
contradiction. Hence $D[X]$ is strong.

Case 2a: $D[X]$ is not biconnected.

Consider $B=(B_{1},\dots,B_{n})$ a longest path of blocks in $D[X]$. Since
$D[X]$ is not biconnected, $n\geq 2$.

Let $V(B_{1})\cap V(B_{2})=\\{a\\}$. There is a digon between
$V(B_{1})\setminus a$ and $\overline{X}$, for otherwise $a$ is a cutvertex of
$D$. Suppose there is only one digon $[b,y]$ between $V(B_{1})\setminus a$ and
$\overline{X}$, with $b\in V(B_{1})\setminus a$ and $y\in\overline{X}$. Then
$D\setminus a-[b,y]$ is not connected, thus by Lemma 5.7, $D$ is a directed
Hajós join or a Hajós bijoin, a contradiction.

Thus we can assume that there are at least two digons between $\overline{X}$
and $V(B_{1})\setminus V(B_{2})$, say $[a_{1},y_{1}]$ and
$[b_{1},y_{1}^{\prime}]$ with $a_{1},b_{1}\in V(B_{1})\setminus V(B_{2})$ and
$y_{1},y_{1}^{\prime}\in\overline{X}$. Similarly, there are two digons between
$\overline{X}$ and $V(B_{n})\setminus V(B_{n-1})$, say $[a_{n},y_{n}]$ and
$[b_{n},y_{n}^{\prime}]$ with $a_{n},b_{n}\in V(B_{n})\setminus V(B_{n-1})$.
Note that $a_{1}=b_{1}$ and $a_{n}=b_{n}$ are possible, but
$y_{1},y^{\prime}_{1},y_{n},y^{\prime}_{n}$ are pairwise distinct by claim
5.7.2. As there are at least $4$ digons between $X$ and $\overline{X}$, we
have $k\geq 4$.

Set $H=B+[a_{1},a_{n}]$ and let us prove that $\lambda(H)=k$.

By Lemma 3.3, $a_{1}$ and $a_{n}$ receive the same colour in all
$k$-dicolouring of $D[X]$, and since any $k$-dicolouring of $B$ can easily be
extended to a $k$-dicolouring of $D[X]$, the same holds for any
$k$-dicolouring of $B$, and thus $\operatorname{\overrightarrow{\chi}}(H)\geq
k+1$. Let $P_{a_{1}a_{n}}=a_{1}\rightarrow y_{1}\rightarrow y_{n}\rightarrow
a_{n}$ and $P_{a_{n}a_{1}}=a_{n}\rightarrow y_{n}\rightarrow y_{1}\rightarrow
a_{1}$. By Lemma 3.5,
$\lambda(D+[a_{1},a_{n}]-A(P_{1})-A(P_{2}))\leq\lambda(D)=k$, and thus
$\lambda(H)\leq k$. Thus
$k+1\leq\operatorname{\overrightarrow{\chi}}(H)\leq\lambda(H)+1\leq k+1$, so
$\lambda(H)=k$.

Hence there are $k$ arc-disjoint $b_{1}b_{n}$-dipaths in $H$. But replacing
any potential use of $a_{1}a_{n}$ by $P_{a_{1}a_{n}}$ and any potential use of
$a_{n}a_{1}$ by $P_{a_{n}a_{1}}$, and considering the dipath $b_{1}\rightarrow
y^{\prime}_{1}\rightarrow y^{\prime}_{n}\rightarrow b_{n}$, we get $k+1$ arc-
disjoint $b_{1}b_{n}$-dipaths in $D$, a contradiction.

Case 2b: $D[X]$ is biconnected.

If a vertex $a\in X$ is adjacent to every vertex in $\overline{X}$, then $a$
is a cutvertex of $D$, a contradiction.

Let $a,b\in X$, $a\neq b$, such that there exist
$a^{\prime},b^{\prime}\in\overline{X}$ with
$[a,a^{\prime}],[b,b^{\prime}]\subseteq A(D)$. If $k=3$, let them be chosen so
that neither $a^{\prime}$ nor $b^{\prime}$ is the center of $D[\overline{X}]$.
Let $D^{\prime}=D[X]+[a,b]$. Since $D[X]$ is strong and biconnected, so is
$D^{\prime}$. By Lemma 3.3,
$\operatorname{\overrightarrow{\chi}}(D^{\prime})\geq k+1$ for in every
$k$-dicolouring $\varphi$ of $D[X]$, $\varphi(a)=\varphi(b)$. By Lemma 3.5,
$\lambda(D^{\prime})\leq\lambda(D)=k$. Thus $D^{\prime}$ is $k$-extremal.

By induction, $D^{\prime}$ is either a symmetric odd wheel, a symmetric
complete graph, a directed Hajós join of two digraphs $D_{1}$ and $D_{2}$ or a
Hajós bijoin of two digraphs $D_{1}$ and $D_{2}$.

If $D^{\prime}$ is a directed Hajós join of two digraphs $D_{1}$ and $D_{2}$,
then either $a,b\in V(D_{1})$ or $a,b\in V(D_{2})$, and thus $D$ is a directed
Hajós join, a contradiction.

If $D^{\prime}$ is a Hajós bijoin of two digraphs $D_{1}$ and $D_{2}$ with
respect to $((t,x_{1},w),(v,x_{2},u))$, then if either $a,b\in V(D_{1})$ or
$a,b\in V(D_{2})$, $D$ is itself a Hajós bijoin, a contradiction. Otherwise,
we have $t=w$, $v=u$ and $\\{t,u\\}=\\{a,b\\}$, which contradicts that $D[X]$
is biconnected.

Thus $D^{\prime}$ is $\overleftrightarrow{K}_{k+1}$ or a symmetric odd wheel.

Suppose there is no vertex in $X\setminus\\{a,b\\}$ with a neighbour in
$\overline{X}$. Then $a$ and $b$ both have at least two neighbours in
$\overline{X}$, for otherwise either $D\setminus[a,a^{\prime}]$ or
$D\setminus[b,b^{\prime}]$ has a cutvertex, and thus by Lemma 5.7, $D$ is a
directed Hajós join or a Hajós bijoin, a contradiction. Note that this implies
that $k\geq 4$. Let $a^{\prime},a^{\prime\prime}\in\overline{X}\cap N(a)$ and
$b^{\prime},b^{\prime\prime}\in\overline{X}\cap N(b)$. Then, since
$\lambda_{D^{\prime}}(a,b)=k$, we have that $\lambda_{D[X]}(a,b)\geq k-1$,
that is there exist $k-1$ arc-disjoint $ab$-dipaths in $D[X]$. But then, since
$a\rightarrow a^{\prime}\rightarrow b^{\prime}\rightarrow b$ and $a\rightarrow
a^{\prime\prime}\rightarrow b^{\prime\prime}\rightarrow b$ are arc-disjoint
$ab$-dipaths that do not use any arc of $D[X]$, we have that
$\lambda_{D}(a,b)\geq k+1$, a contradiction.

Thus, there exists a vertex $c\in X\setminus\\{a,b\\}$ with a neighbour
$c^{\prime}\in\overline{X}$. Observe that $c$ is not adjacent with $a$ nor
$b$, for either $[a,c]\in A(D)$ or $[b,c]\in A(D)$ (because
$D^{\prime}=D[X]+[a,b]$ is symmetric) and in any $k$-dicolouring $\varphi$ of
$D[X]$, $\varphi(a)=\varphi(b)=\varphi(c)$ by Lemma 3.3, a contradiction. This
implies that $D^{\prime}\neq\overleftrightarrow{K}_{k+1}$, and thus $k=3$ and
$D^{\prime}$ is a symmetric odd wheel. Let $x$ be the center of $D^{\prime}$.
Since $c$ is neither a neighbour of $a$ nor of $b$, we have that
$x\notin\\{a,b,c\\}$. Let $d,e$ be the two other neighbours of $c$ in $D$.
Then, $x\rightarrow d\rightarrow c$, $x\rightarrow e\rightarrow c$,
$x\rightarrow a\rightarrow a^{\prime}\rightarrow c^{\prime}\rightarrow c$ and
$x\rightarrow c$ are $4>k$ arc-disjoint $xc$-dipaths, a contradiction.

##  6 Hajós tree joins - Structure Theorems

At the end of this section, we will prove the main result of this article:
$k$-extremal digraphs are exactly the digraphs in $\vec{\mathcal{H}}_{k}$,
which we recall is a class built from $\overleftrightarrow{K}_{k+1}$ (for
$k\geq 4$) or symmetric odd wheels (for $k=3$) using directed Hajós joins and
Hajós tree joins. In order to simplify our arguments, we will prove in fact an
equivalence with another class called $\vec{E\mathcal{HT}}_{k}$ that is based
on a single operation called extended Hajós tree join (which generalizes both
Hajós tree joins and directed Hajós join) defined below. See Figure 5.

An Euler tour is a closed trail that traverses each arc exactly once. Let $T$
be a tree. An Eulerian list $C$ of $T$ is the circular list of the vertices of
$T$ encountered following an Eulerian tour of $\overleftrightarrow{T}$ (note
that there is a unique such circular list). A partial Eulerian list
$C^{\prime}$ of $T$ is a circular sublist of an Eulerian list of $T$ with the
following properties:

  * •

each leaf of $T$ is in $C^{\prime}$, and

  * •

each non-leaf vertex of $T$ appears at most once in $C^{\prime}$.

######  Definition 6.1 (Extended Hajós tree join).

Given

  * •

a tree $T$ with edges $\\{u_{1}v_{1},\dots,u_{n}v_{n}\\}$

  * •

a partial Eulerian list $C=(x_{1},\dots,x_{\ell})$ of $T$, and

  * •

for $i=1,\dots,n$, $D_{i}$ a digraph such that

    * –

$V(D_{i})\cap V(T)=\\{u_{i},v_{i}\\}$,

    * –

$[u_{i},v_{i}]\subseteq A(D_{i})$, and

    * –

for $1\leq i\neq j\leq n$, $V(D_{i})\setminus\\{u_{i},v_{i}\\}\cap
V(D_{j})\setminus\\{u_{j},v_{j}\\}=\emptyset$.

We define the extended Hajós tree join $T(D_{1},\dots,D_{n};C)$ to be the
digraph $D$ obtained from $D_{i}-[a_{i},b_{i}]$ for $i=1,\dots,n$ by adding
the dicycle $C=x_{1}\rightarrow x_{2}\rightarrow\dots\rightarrow
x_{\ell}\rightarrow x_{1}$.

We say that $D$ is the extended Hajós tree join of $(T,D_{1},\dots,D_{n})$
with respect to $C$.

$C$ is called the peripheral cycle of $D$ and vertices
$u_{1},v_{1},\dots,u_{n},v_{n}$ are the junction vertices of $D$ (note that
there are $n-1$ of them).

$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$T$$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$D$
Figure 5: A cartoonish drawing of an extended Hajós tree join $D$. Its
peripheral cycle is in red. Removed digons are in dashed green. $T$ is the
corresponding tree.

Observe that an extended Hajós tree join in which the partial Eulerian list
only uses leaves of $T$ is a Hajós tree join. Observe also that the peripheral
cycle may be a digon in the case where $T$ is a path and the partial Eulerian
list only contains the extremities of $T$. Note that every digraph $D$ that
contains a digon is an extended Hajnal tree join of itself, as if we denote by
$T$ the tree consisting of the single edge $uv$, then we have the trivial
identity $D=T(D,[uv])$.

We denote by $W_{\ell}$ the wheel on $\ell+1$ vertices.

######  Definition 6.2 (The class $\vec{E\mathcal{HT}}_{k}$).

For $k\geq 4$, let $\vec{E\mathcal{HT}}_{k}$ be the smallest class of digraphs
that contains $\overleftrightarrow{K}_{k+1}$ and is closed under taking
extended Hajós tree joins. Let $\vec{E\mathcal{HT}}_{3}$ be the smallest class
of digraphs that contains $\overleftrightarrow{W}_{2\ell+1}$, for every
integer $\ell\geq 1$, and is closed under taking extended Hajós tree joins.

The two following lemmata imply (by induction on the number of vertices) that
$\vec{E\mathcal{HT}}_{k}\subseteq\vec{\mathcal{H}}_{k}$.

######  Lemma 6.3.

Let $k\geq 3$. Let $D\in\vec{E\mathcal{HT}}_{k}$, $D$ distinct from a
symmetric complete digraph and a symmetric odd wheel. Then $D$ is either a
directed Hajós join or a Hajós tree join of digraphs in
$\vec{E\mathcal{HT}}_{k}$.

###### Proof.

Denote $D=T(D_{1},\dots,D_{n};C)$ as in Definition 6.1. If $C$ does not use
any internal vertex of $T$, then $D$ is a Hajós tree join and we are done. So
we can assume $C$ uses an internal vertex $v$ of $T$. Let $X$ be the connected
component of $T\setminus v$ that contains the out-neighbour of $v$ in $C$. Let
$\mathcal{L}_{1}$ be the list of digraphs corresponding to the edges of
$T[X\cup v]$, and
$\mathcal{L}_{2}=\\{D_{1},\dots,D_{n}\\}\setminus\mathcal{L}_{1}$. As $C$ is a
partial Eulerian list, which is thus obtained from an Eulerian tour, it is of
the form $C=vP_{X}P_{\overline{X}}$ where $P_{X}$ is the portion of $C$
contained in $X$, and $P_{\overline{X}}$ is the portion of $C$ contained in
$V(T)\setminus(X\cup v)$. Note that, since $v$ is a cutvertex of $T$, $P_{X}$
and $P_{\overline{X}}$ are non-empty

Let $x$ be the last vertex of $P_{X}$ and $y$ be the first element of
$P_{\overline{X}}$. Then $D\setminus v-xy$ is disconnected, and thus $D$ is a
directed Hajós join of
$D^{\prime}_{1}=D[\bigcup_{G\in\mathcal{L}_{1}}V(G)]+xv$, and
$D^{\prime}_{2}=D[\bigcup_{G\in\mathcal{L}_{2}}V(G)]+vy$, which are clearly in
$\vec{E\mathcal{HT}}_{k}$.

∎

######  Lemma 6.4.

Let $k\geq 3$. A directed Hajós join of two digraphs in
$\vec{E\mathcal{HT}}_{k}$ is in $\vec{E\mathcal{HT}}_{k}$.

###### Proof.

Let $D$, $D^{\prime}$ be two digraphs in $\vec{E\mathcal{HT}}_{k}$, $uv_{1}\in
A(D)$, $v_{2}w\in A(D^{\prime})$ and let $H$ be the directed Hajós join of $D$
and $D^{\prime}$ with respect to $(uv_{1},v_{2}w)$. We call $v$ the vertex
obtained after identifying $v_{1}$ and $v_{2}$. We want to prove that
$H\in\vec{E\mathcal{HT}}_{k}$. We distinguish four cases.

Case 1: $D=D^{\prime}=\overleftrightarrow{K}_{k+1}$ or
$D=\overleftrightarrow{W}_{2\ell+1}$ and
$D^{\prime}=\overleftrightarrow{W}_{2\ell^{\prime}+1}$ for some
$\ell,\ell^{\prime}\geq 1$.
Let $T=(\\{u,v,w\\},\\{uv,vw\\})$ be the path of length $2$ and let
$C=u\rightarrow v\rightarrow w\rightarrow u)$. Observe that $(u,v,w,u)$ is a
partial Eulerian list of $T$. Then it is easy to check that
$T(D,D^{\prime};C)$ is the directed Hajós join of $D$ and $D^{\prime}$. See
Figure 6. This proves Case 1.

uvw Figure 6:  The directed Hajós join of two $\overleftrightarrow{K}_{4}$.

From now on, we may assume that $D=T(D_{1},\dots,D_{n^{\prime}};C)$ for some
tree $T$, some digraphs $D_{1},\dots,D_{n}$ and a peripheral cycle $C$ built
from a partial Eulerian list $L$ of $T$.

Case 2: $uv_{1}\notin A(C)$.
In this case, there is $i\in[n]$ such that $uv_{1}\in A(D_{i})$. By induction,
there exists $H^{\prime}\in\vec{E\mathcal{HT}}_{k}$ such that $H^{\prime}$ is
the directed Hajós join of $D_{i}$ and $D^{\prime}$ with respect to
$(uv_{1},v_{2}w)$. Then
$H=T(D_{1},\dots,D_{i-1},H^{\prime},D_{i+1},\dots,D_{n};C)\in\vec{E\mathcal{HT}}_{k}$.
This proves Case 2.

Case 3: $uv_{1}\in A(C)$ and $D^{\prime}$ is a symmetric complete graph or a
symmetric odd wheel.
In particular, $u$ and $v_{1}$ are vertices of $T$. Then
$H=T^{\prime}(D_{1},\dots,D_{n},D^{\prime};C^{\prime})\in\vec{E\mathcal{HT}}_{k}$,
where $T^{\prime}$ is obtained from $T$ by adding the vertex $w$ and the edge
$v_{1}w$, and $C^{\prime}$ is obtained from the partial Eulerian list
$L^{\prime}$ obtained from $L$ by adding $w$ between $u$ and $v_{1}$ (in other
words the peripheral cycle $C^{\prime}$ is obtained from $C$ by deleting
$uv_{1}$ and adding $uw$ and $wv_{1}$). This proves Case 3.

Case 4: $uv_{1}\in A(C)$ and $D^{\prime}$ is neither a symmetric complete
graph nor a symmetric odd wheel.
Then
$D^{\prime}=T^{\prime}(D^{\prime}_{1},\dots,D^{\prime}_{n^{\prime}};C^{\prime})$
for some tree $T^{\prime}$, some digraphs
$D^{\prime}_{1},\dots,D^{\prime}_{n^{\prime}}$ and a peripheral cycle
$C^{\prime}$ built from a partial Eulerian list $L^{\prime}$ of $T$.

If $v_{2}w\notin A(C^{\prime})$, then the result follows from Case 2. So we
may assume that $v_{2}w\in A(C^{\prime})$.

Since $uv_{1}\in A(C)$ and $v_{2}w\in A(C^{\prime})$, we have
$L=(u,v_{1},L_{1},u)$ and $L^{\prime}=(v_{2},w,L^{\prime}_{1},v_{2})$ for some
lists $L_{1}$ and $L^{\prime}_{1}$.

Let $T_{H}$ be the tree obtained from $T$ and $T^{\prime}$ by identifying
$v_{1}$ and $v_{2}$ to a new vertex $v$. Then
$H=T_{H}(D_{1},\dots,D_{n},D^{\prime}_{1},\dots,D^{\prime}_{n^{\prime}};C_{H})$,
where $C_{H}$ is obtained from the partial Eulerian list
$L_{H}=(v,L_{1},u,w,L_{2},v)$. This proves Case 4 and the lemma. ∎

The following result is crucial, as it will allow us to use Hajós bijoins
given by Theorem 5.1 and preserve the fact of being in
$\vec{E\mathcal{HT}}_{k}$ (this is the main reason why extended Hajós tree
joins are more convenient to use that Hajós tree join combined with directed
Hajós join).

######  Lemma 6.5.

Let $k\geq 3$. Let $D\in\vec{E\mathcal{HT}}_{k}$ and $uv,vw\in A(D)$ with
$u\neq w$. If in all $k$-dicolourings of $D\setminus\\{uv,vw\\}$ there is a
monochromatic $wu$-dipath, then $D=T(D_{1},\dots,D_{n};C)$ such that $uv$ and
$vw$ are in $A(C)$.

###### Proof.

Assume that in all $k$-dicolourings of $D\setminus\\{uv,vw\\}$ there is a
monochromatic $wu$-dipath. Assume that the result holds for every digraph in
$\vec{E\mathcal{HT}}_{k}$ with strictly less vertices than $D$.

Assume first that $D$ is a symmetric complete graph or a symmetric odd wheel.
Let $\varphi$ be a $k$-dicolouring of $D-uv$ (which must exist for $D$ is
dicritical). Then $w$ has a colour distinct from the colours of each of its
neighbours with respect to $\varphi$, and thus $\varphi$ is a $k$-dicolouring
of $D-\\{uv,vw\\}$ in which there is no monochromatic $wu$-dipath. So we may
assume that $D$ is not a symmetric complete graph nor a symmetric odd wheel.

Thus, $D=T(D_{1},\dots,D_{n};C)$ and let $\\{u_{i},v_{i}\\}=V(D_{i})\cap V(T)$
for $i=1,\dots,n$. Assume for contradiction that, $uv\notin E(C)$ or $vw\notin
E(C)$.

Case 1: $u\in V(D_{i})\setminus\\{u_{i},v_{i}\\}$ for some $i\in[n]$,
$v=v_{i}$, and $w\notin V(D_{i})\setminus\\{u_{i}\\}$.
In this case, we will find a $k$-dicolouring of $D\setminus\\{uv,vw\\}$ with
no monochromatic $wu$-dipath, thus obtaining a contradiction. Since $D$ is
$(k+1)$-dicritical, there is a $k$-dicolouring $\varphi$ of $D\setminus
uv_{i}$. Since $\varphi$ is, in particular, a $k$-dicolouring of
$D\setminus\\{uv_{i},v_{i}w\\}$, it contains a monochromatic $wu$-dipath $P$
by hypothesis. Hence $\varphi(u)=\varphi(w)$. Since $w\notin
V(D_{i})\setminus\\{u_{i}\\}$, $P$ goes through $u_{i}$ or $v_{i}$.

Observe first that $\varphi(u)=\varphi(v_{i})$, for otherwise $\varphi$ is a a
$k$-dicolouring of $D$, a contradiction. If $P$ goes through $v_{i}$, the arc
$v_{i}w$ yields a monochromatic directed cycle, a contradiction. Hence $P$
foes through $u_{i}$. Hence, $\varphi(u_{i})=\varphi(u)=\varphi(v_{i})$. This
implies that all junction vertices receive the same colour, and thus the
peripheral cycle is monochromatic, a contradiction. This proves case 1.

Case 2: $u,v,w\in V(D_{i})$ for some $i\in[n]$, $uv\notin A(C)$ and $vw\notin
A(C)$.
Note that, since $uv,vw\notin A(C)$,
$\\{uv,vw\\}\cap\\{u_{i}v_{i},v_{i}u_{i}\\}=\emptyset$.

Suppose first that
$D_{i}=T^{\prime}\big{(}D^{\prime}_{1},\dots,D^{\prime}_{m};C^{\prime}\big{)}$
with $uv\in A(C^{\prime})$ and $vw\in A(C^{\prime})$. As $u\neq w$,
$|V(C)|\geq 3$, and thus there exists $j$ such that $[u_{i},v_{i}]\in
D^{\prime}_{j}$. Then:

$D=T^{\prime}\big{(}D^{\prime}_{1},\dots,D^{\prime}_{j-1},T\big{(}D_{1},\dots,D_{i-1},D^{\prime}_{j},D_{i+1},\dots,D_{n};C\big{)},D^{\prime}_{j+1},\dots,D^{\prime}_{m};C^{\prime}\big{)}$

and we are done.

So $uv$ or $vw$ is not in $A(C)$. Hence, by induction, there is a
$k$-dicolouring $\varphi_{i}$ of $D_{i}\setminus\\{uv,vw\\}$ such that there
is no monochromatic $wu$-dipath in $D_{i}$. Observe that
$\varphi_{i}(u_{i})\neq\varphi_{i}(v_{i})$ since $u_{i}$ and $v_{i}$ are
linked by a digon in $D_{i}\setminus\\{uv,vw\\}$.

Now, let $\varphi$ be a $k$-dicolouring of
$D\setminus\big{(}V(D_{i})\setminus\\{u_{i},v_{i}\\}\big{)}$. If
$\varphi(u_{i})=\varphi(v_{i})$, then all junction vertices receive this same
colour, and $C$ is monochromatic, a contradiction. So
$\varphi(u_{i})\neq\varphi(v_{i})$. Now, we may assume without loss of
generality that $\varphi(u_{i})=\varphi_{i}(u_{i})$ and
$\varphi(v_{i})=\varphi_{i}(v_{i})$, and obtain a $k$-dicolouring of
$D\setminus\\{uv,vw\\}$ with no monochromatic $wu$-dipath. Indeed, a
$wu$-dipath is either included in $D_{i}-[u_{i},v_{i}]$, or contains both
$u_{i}$ and $v_{i}$.

Let us now explain why these two cases cover all possible cases. Since
$uv\notin E(C)$ or $vw\notin E(C)$, we may assume that at least one vertex of
$\\{u,v,w\\}$ is not a junction vertex, for an arc linking two junction
vertices is an arc of $C$.

  * •

If none of $\\{u,v,w\\}$ is a junction vertex, we are in case 2.

  * •

If $v$ is a junction vertex and $u$ is not. Then $u\in
V(D_{i})\setminus\\{u_{i},v_{i}\\}$ for some $i\in[n]$. Then either $w\notin
V(D_{i})\setminus\\{u_{i}\\}$, and we are in case 1, or $w\in
V(D_{i})\setminus u_{i}$, and we are in case 2.

  * •

By directional duality, the previous case is the same as the case where $v$ is
a junction vertex and $w$ is not.

  * •

If $v$ is not a junction vertex, then $v\in
V(D_{i})\setminus\\{u_{i},v_{i}\\}$ for some $i\in[n]$, and thus $u,w\in
V(D_{i})$, and we are in case 2.

∎

From the previous lemma, we deduce an analogous of Lemma 6.4 for Hajós
bijoins.

######  Lemma 6.6.

Let $k\geq 3$. If $D$ is not $k$-dicolourable and $D$ is the Hajós bijoin of
two digraphs $D_{1}\in\vec{E\mathcal{HT}}_{k}$ and
$D_{2}\in\vec{E\mathcal{HT}}_{k}$, then $D\in\vec{E\mathcal{HT}}_{k}$.

###### Proof.

Let $ta_{1},a_{1}w\in A(D_{1})$, and $t$ and $w$ are in the same connected
component of $D_{1}\setminus a_{1}$. Let $va_{2},a_{2}u\in A(D_{2})$, and $u$
and $v$ are in the same connected component of $D_{2}\setminus a_{2}$. Assume
that $D$ is obtained from the disjoint union of $D_{1}-\\{ta_{1},a_{1}w\\}$
and $D_{2}-\\{va_{2},a_{2}u\\}$ by identifying $a_{1}$ and $a_{2}$ into a new
vertex $a$, and adding the arcs $tu$ and $vw$, i.e. $D$ is the bijoin of
$D_{1}$ and $D_{2}$ with respect to $((t,a_{1},w),(u,a_{2},v))$.

Suppose first that $t\neq w$ and $D_{1}-\\{ta_{1},a_{1}w\\}$ admits a
$k$-dicolouring $\varphi_{1}$ with no monochromatic $wt$-dipath. Then either
there is no monochromatic $wa_{1}$-dipath, or no monochromatic
$a_{1}t$-dipath. Without loss of generality, suppose there is no monochromatic
$wa_{1}$-dipath. As $D_{2}$ is $(k+1)$-dicritical, $D_{2}-va_{2}$ is
$k$-dicolourable, and thus there is a $k$-dicolouring $\varphi_{2}$ of
$D_{2}-\\{va_{2},a_{2}u\\}$ with no monochromatic $ua_{2}$-dipath. Up to
permuting colours, we may assume that $\varphi_{1}(a_{1})=\varphi_{2}(a_{2})$.
Consider $\varphi:V(D)\rightarrow[k]$ such that

$\varphi(x)=\left\\{\begin{array}[]{ll}\varphi_{1}(a_{1})&\text{ if }x=a\\\
\varphi_{1}(x)&\text{ if }x\in V(D_{1})\\\ \varphi_{2}(x)&\text{ if }x\in
V(D_{2})\end{array}\right.$

Since $\operatorname{\overrightarrow{\chi}}(D)\geq k+1$, $\varphi$ contains a
monochromatic dicycle $C$. Since $\varphi_{1}$ and $\varphi_{2}$ are
$k$-dicolourings of respectively $D[V(D_{1})]$ and $D[V(D_{2})]$, $C$
intersects both $V(D_{1})\setminus a_{1}$ and $V(D_{2})\setminus a_{2}$. Thus
it contains $tu$, or $vw$ or both.
If $C$ contains $tu$ but not $vw$, then $C$ goes through $a$, and thus there
is a monochromatic $ua_{2}$-dipath in $D_{2}$, which together with $a_{2}u$
forms a monochromatic dicycle in $D_{2}$ with respect to $\varphi_{2}$ a
contradiction to the choice of $\varphi_{2}$.
If $C$ contains $vw$ but not $tu$, then there is a monochromatic $wa$-dipath
in $D_{1}$ with respect to $\varphi_{1}$, a contradiction to the choice of
$\varphi_{1}$.
Hence $C$ contains both $tu$ and $vw$ and thus there is a monochromatic
$wt$-dipath in $D_{1}$, a contradiction to the choice of $\varphi_{1}$.

Hence, if $t\neq w$, then all $k$-dicolourings of $D_{1}-\\{ta_{1},a_{1}w\\}$
admit a monochromatic $wt$-dipath. Similarly, if $u\neq v$ then all
$k$-dicolourings of $D_{2}-\\{va_{2},a_{2}u\\}$ admit a monochromatic
$uv$-dipath.

If $t=w$, then in fact we can write $D_{1}=T^{1}(D^{1},[ta1])$, where $T^{1}$
is simply the tree consisting of the edge $ta_{1}$. Otherwise by Lemma 6.5,
$D_{1}=T^{1}(D^{1}_{1},\dots,D^{1}_{n};C^{1})$ for a tree $T^{1}$, digraphs
$D^{1}_{1},\dots,D^{1}_{n}$ and peripheral cycle $C^{1}$ such that $ta_{1}$
and $a_{1}w$ are in $A(C^{1})$. Similarly, either $u=v$ in which case we write
$D_{2}=T^{2}(D_{2},[a2u])$ with $T_{2}$ being the tree consisting of the
single edge $a_{2}u$, or $D_{2}=T^{2}(D^{2}_{1},\dots,D^{2}_{m};C^{2})$ for a
tree $T^{2}$, digraphs $D^{2}_{1},\dots,D^{2}_{m}$ and peripheral cycle
$C^{2}$ such that $va_{2}$ and $a_{2}u$ are in $A(C^{2})$. In all cases let
$T$ be the tree obtained from $T_{1}$ and $T_{2}$ by identifying $a_{1}$ and
$a_{2}$ to a vertex $a$. Now,
$D=T(D^{1}_{1},\dots,D^{1}_{n},D^{2}_{1},\dots,D^{2}_{m};C)$ where $C$ is
obtained from $C_{1}$ and $C_{2}$ after deleting arcs $ta_{1}$, $a_{1}w$,
$va_{2}$ and $a_{2}w$, and adding $tu$ and $vw$.

∎

For the proof of our main theorem, we need to prove that digraphs in
$\vec{\mathcal{H}}_{k}$ are indeed $k$-extremal. We know directed Hajós joins
preserve $k$-extremality (Lemma 5.3), we do it now for Hajós tree joins (we
prove an if and only if for the purpose of the recognition algorithm of the
next section)

######  Lemma 6.7.

Let $k\geq 2$. Let $D,D_{1},\dots,D_{n}$ be digraphs such that $D$ is a Hajós
tree join of the $D_{i}$. Then $D$ is $k$-extremal if and only if all digraphs
$D_{1},\dots,D_{n}$ are $k$-extremal.

###### Proof.

Let $D=T(D_{1},\dots,D_{n};C)$ where $T$, $C$, $D_{1},\dots,D_{n}$ are as in
Definition 1.6. For each $D_{i}$, let $\\{u_{i},v_{i}\\}=V(T)\cap V(D_{i})$
such that the digon $[u_{i},v_{i}]$ is in $A(D_{i})$ but was removed in the
construction of $D$.

Let $D^{\prime}$ the digraph obtained from $D$ by putting back all digons
$[u_{i},v_{i}]$ between vertices of $T$, and by removing the arcs in the
peripheral cycle $C$. $D^{\prime}$ is a digraph whose blocks are exactly the
$D_{i}$. One can easily observe that
$\lambda(D^{\prime})=\max_{i=1}^{n}\lambda(D_{i})$ and
$\operatorname{\overrightarrow{\chi}}(D^{\prime})=\max_{i=1}^{n}\operatorname{\overrightarrow{\chi}}(D_{i})$.
For every arc $uv\in A(C)$, let $P_{uv}$ be the unique $uv$-dipath of
$D^{\prime}$ that uses only arcs between vertices of $T$ (arcs from the digons
that were removed to construct $D$). It is easy to notice that all $P_{uv}$
are pairwise arc-disjoint (each cycle $uv+P_{uv}$ correspond to one face of
the planar graph $T+C$). Therefore one can go from $D^{\prime}$ to $D$ by
applying successive operations where one replaces the $uv$-dipath $P_{uv}$ by
the arc $uv$ for each arc $uv\in A(C)$. By Lemma 3.5, we obtain
$\lambda(D)\leq\lambda(D^{\prime})=\max_{i=1}^{n}\lambda(D_{i})$.

Assume $D$ is $k$-dicolourable. Then in any $k$-dicolouring of $D$, the
vertices of $T$ do not all get the same colour (otherwise $C$ would me
monochromatic). So there is a digraph $D_{i}$ such that the vertices $u_{i}$
and $v_{i}$ get distinct colours. But this provides a proper $k$-dicolouring
of the corresponding $D_{i}$. Hence, if $D$ is $k$-dicolourable, then
$\min_{i=1}^{n}\operatorname{\overrightarrow{\chi}}(D_{i})\leq k$.

With the two previous paragraphs, we can already prove that if each $D_{i}$ is
$k$-extremal, then $D$ is $k$-extremal. We have
$\operatorname{\overrightarrow{\chi}}(D_{i})=k+1=\lambda(D_{i})+1$ for every
$i$. So, by the first paragraph, $\lambda(D)\leq k$, and by the second
paragraph, $k+1\leq\operatorname{\overrightarrow{\chi}}(D)$. Hence
$k+1\leq\operatorname{\overrightarrow{\chi}}(D)\leq\lambda(D)+1\leq k+1$, so
$\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$. If $D$ admits a
cutvertex, then by construction of the Hajós tree join, a block is included in
some $D_{i}$, which contradicts the fact that $D_{i}$ is biconnected. Now
observe that since every $D_{i}$ is Eulerian (for they are $k$-extremal), $D$
is also Eulerian and is thus strong.

Now assume $D$ is $k$-extremal. If for some $i\in[n]$, $D_{i}$ is not
connected (resp. has a cutvertex), then at least one connected component
(resp. block) is disjoint from $\\{u_{i},v_{i}\\}$ (recall that
$[u_{i},v_{i}]\subseteq A(D_{i})$), and we get that $D$ is also not connected
(resp. has a cutvertex); a contradiction. So each $D_{i}$ is biconnected.

Since $D$ is Eulerian, every $D_{i}$ is also Eulerian and thus every $D_{i}$
is strong.

Let $i\in[n]$ and let us prove that $\lambda(D_{i})=k$. Let $u,v\in V(D_{i})$,
and set $\lambda_{D_{i}}(u,v)=p$, i.e. there is $p$ arc-disjoint $uv$-dipaths
in $D_{i}$. Then either these dipaths do not use any arc in the digon
$[u_{i},v_{i}]$, in which case these dipaths are still present in $D$, or they
do use one of the arcs $\\{u_{i}v_{i},v_{i}u_{i}\\}$, but then we can assume
they don’t use both, for otherwise we could reroute the dipaths to obtain a
collection of $uv$-dipaths that do not use any arc in the digon
$[u_{i},v_{i}]$. But then we can replace this arc by a $u_{i}v_{i}$-dipath or
$v_{i}u_{i}$-dipath using only arcs in some $D_{j}$ for $j\neq i$ and some
peripheral arcs of $C$. Hence we still get $p$ pairwise arc disjoint
$uv$-dipaths. Therefore $\max_{i=1}^{n}\lambda(D_{i})\leq\lambda(D)$, so
$\lambda(D_{i})\leq k$ for every $i$.

In order to conclude that every $D_{i}$ is extremal, and since
$\operatorname{\overrightarrow{\chi}}$ is always at most $1+\lambda$ for any
digraph, we only need to prove that
$\operatorname{\overrightarrow{\chi}}(D_{i})>k$ for every $i$.

######  Claim 6.7.1.

If $T$ is a tree and $A^{\prime}\subsetneq A(T)$, there exists
$\varphi:V(T)\to\\{1,2,3\\}$ such that each edge in $A^{\prime}$ is
monochromatic, no edge in $A(T)\setminus A(T^{\prime})$ is monochromatic, and
the leaves of $T$ do not all receive the same colour.

Proof of Claim : Let $uv$ be an edge not in $A^{\prime}$ and consider the two
connected components $T_{u}$ and $T_{v}$ of $T-uv$. If some connected
component only contains edges in $A^{\prime}$ we colour it with one single
colour. If not we apply induction. Up to permuting the colours we can do so
that $u$ and $v$ receive distinct colours. If we applied induction to either
$T_{u}$ or $T_{v}$, then all leaves do not get the same colour, and if not it
means all edges of $T$ except $uv$ was in $A^{\prime}$, but in that case since
the colour of $u$ is distinct from the colour of $v$, the leaves in $T_{u}$
and $T_{v}$ must get distinct colours. $\square$

Now, let $A^{\prime}$ be the set of edges $u_{i}v_{i}$ of $T$ such that
$\operatorname{\overrightarrow{\chi}}(D_{i})=k+1$. If all edges are in
$A^{\prime}$, then we are done. So we may assume for contradiction that it is
not the case. By the claim above, there exists
$\varphi:V(T)\rightarrow\\{1,2,3\\}$ such that each edge of $T^{\prime}$ is
monochromatic, no edge of $A(T)\setminus A^{\prime}$ is monochromatic, and the
leaves of $T$ do not all receive the same colour.

If $u_{i}v_{i}\in A^{\prime}$, then the digraph $D_{i}$ is $k$-extremal and we
can apply Lemma 4.3 to get a $k$-dicolouring $\varphi_{i}$ of
$D_{i}-[u_{i},v_{i}]$ chosen such that
$\varphi_{i}(u_{i})=\varphi_{i}(v_{i})=\varphi(u_{i})$ and such that there are
no monochromatic dipath between $u_{i}$ and $v_{i}$.

If $u_{i}v_{i}\not\in A^{\prime}$, then
$\operatorname{\overrightarrow{\chi}}(D_{i})\leq k$ and we let $\varphi_{i}$
be a $k$-dicolouring of $D_{i}$. Since the digon $[u_{i}v_{i}]$ is in $D_{i}$
$u_{i}$ and $v_{i}$ get distinct colours and we can choose $\phi_{i}$ such
that $\varphi_{i}(u_{i})=\varphi(u_{i})\neq\varphi(v_{i})=\varphi_{i}(v_{i})$.

Altogether, we obtain a $k$-dicolouring of the vertices of $D$ that is proper
on each $D_{i}-[u_{i},v_{i}]$, and such that there is no monochromatic dipath
between any pair of vertices of $T$, and such that $C$ is not monochromatic.
This is a $k$-dicolouring of $D$, our final contradiction.

∎

We are now ready to prove our main theorem.

######  Theorem 6.8.

Let $k\geq 3$ and let $D$ be a digraph. The three following statements are
equivalent:

(i)

$D$ is $k$-extremal

(ii)

$D\in\vec{E\mathcal{HT}}_{k}$

(iii)

$D\in\vec{\mathcal{H}}_{k}$

###### Proof.

If $D$ is a symmetric complete digraph of a symmetric odd wheel, then the
result holds, so assume it is not. We prove the statements by induction on the
number of vertices of $D$.

(i)$\Rightarrow$ (ii)

Assume $D$ is $k$-extremal. By Theorem 5.1, $D$ is either a directed Hajós
join or a Hajós bijoin of two $k$-extremal digraphs.

Assume first that $D$ is the directed Hajós join of two digraphs $D_{1}$ and
$D_{2}$. By Lemma 5.3, both $D_{1}$ and $D_{2}$ are $k$-extremal. Thus by
induction $D_{1}$ and $D_{2}$ belong to $\vec{E\mathcal{HT}}_{k}$ and since
directed Hajós joins preserve the fact of being in $\vec{E\mathcal{HT}}_{k}$
(Lemma 6.4), $D$ is in $\vec{E\mathcal{HT}}_{k}$.

So we can assume that $D$ is a Hajós bijoin of two $k$-extremal digraphs
$D_{1}$ and $D_{2}$. By Lemma 5.5, both $D_{1}$ and $D_{2}$ are $k$-extremal.
So by induction hypothesis they both belong to $\vec{E\mathcal{HT}}_{k}$. By
Lemma 6.6, $D$ is in $\vec{E\mathcal{HT}}_{k}$.

(ii)$\Rightarrow$ (iii)

By Lemma 6.3 a digraph $D$ in $\vec{E\mathcal{HT}}_{k}$ is either a directed
Hajós join or a Hajós tree join of digraphs in $\vec{E\mathcal{HT}}_{k}$ and
thus in $\vec{\mathcal{H}}_{k}$ by induction. Hence $D$ is in
$\vec{\mathcal{H}}_{k}$.

(iii)$\Rightarrow$ (i)

This is guaranteed by the fact that both directed Hajós joins and Hajós tree
joins preserve the fact of being $k$-extremal (Lemmata 5.3 and 6.7).

∎

##  7 Recognition algorithm

In this section, we give a polynomial time algorithm deciding if a given
digraph $D$ satisfies $\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1$.
For algorithmic reasons, we need to avoid Hajós tree joins, so we need to
devise another characterization, using the notion of parallel Hajós joins that
we define now.

######  Definition 7.1 (Parallel Hajós join).

Let $D_{B}$ be a digraph, set $B=V(D_{B})$ and let $[a,b]\subseteq A(D_{B})$.
Let $D_{AC}$ be a digraph with $V(D_{AC})=A\cup C$, $A\cap C=\\{x\\}$, let
$t,w\in A\setminus x$ such that $t,w$ are in the same connected component of
$D_{AC}\setminus x$, and let $u,v\in V(C)$ such that $u$ and $v$ are in the
same connected component of $D_{AC}[C]\setminus x$.
The parallel Hajós join $D$ of $D_{AC}$ and $D_{B}$ with respect to
$(t,u,v,w,[a,b])$ is the digraph obtained from disjoint copies of
$D_{B}-[a,b]$, $D_{AC}[A]$ and $D_{AC}[C]$, by identifying the copy of $x$ in
$D_{AC}[A]$ to $a$, and the copy of $x$ in $D_{AC}[C]$ to $b$. See Figure 7.

$a$$t$$w$$A\setminus x\cup a$$b$$a$$B$$D$$b$$u$$v$$C\setminus x\cup
b$$x$$t$$w$$A$$x$$u$$v$$C$$D_{AC}$$b$$a$$B$$D_{B}$ Figure 7: $D$ is a parallel
Hajós join of $D_{AC}$ and $D_{B}$ with respect to $(t,u,v,w)$.

Let us say an informal word on the intuition behind parallel Hajós join. Let
$D=T(D_{1},\dots,D_{n};C)$ be a Hajós tree join and assume $u_{i}v_{i}\in
E(T)$ is such that both $u_{i}$ and $v_{i}$ are interior vertices of $T$. Then
$D$ is the Hajós parallel join of $D_{i}$ and the Hajós tree join obtained
after contracting $D_{i}$.

As before, we need to prove that this operation preserves extremality.

######  Lemma 7.2.

Let $k\geq 3$. A parallel Hajós join of two digraphs $D_{AC}$ and $D_{C}$ is
$k$-extremal if and only if both $D_{AC}$ and $D_{B}$ are $k$-extremal.

###### Proof.

Let $D$ be the parallel Hajós join of $D_{AC}$ and $D_{B}$ as in Definition
7.1.

Let $D_{A}=D[A]+\\{ta,aw\\}$, $D_{C}=D[C]+\\{vb,bu\\}$ and $D_{BC}=D[V(B)\cup
V(C)]+\\{va,au\\}$. See Figure 8.

$a$$t$$w$$A$$D_{A}$$b$$a$$B$$D_{B}$$b$$u$$v$$C$$D_{C}$$b$$a$$B$$b$$u$$v$$C\setminus
x\cup b$$D_{BC}$ Figure 8: $D_{A}$, $D_{B}$, $D_{C}$ and $D_{BC}$ in the proof
of Lemma 7.2.

Observe that

  * •

$D$ is a degenerated Hajós bijoin of $D_{A}$ and $D_{BC}$,

  * •

$D_{BC}$ is a degenerated Hajós bijoin of $D_{B}$ and $D_{C}$, and

  * •

$D_{AC}$ is a Hajós bijoin of $D_{A}$ and $D_{C}$.

Suppose first that $D$ is $k$-extremal ane let us prove that $D_{AC}$ and
$D_{B}$ are $k$-extremal.

Since $D$ is a Hajós bijoin of $D_{A}$ and $D_{BC}$, and $D_{BC}$ is a
degenerated Hajós bijoin of $D_{B}$ and $D_{C}$, we get that $D_{A}$ and
$D_{B}$ and $D_{C}$ are $k$-extremal by Lemma 5.5. So it remains to prove that
$D_{AC}$ is $k$-extremal.

Since $D_{A}$ and $D_{C}$ are $k$-extremal, and $D_{AC}$ is the Hajós bijoin
of $D_{A}$ and $D_{C}$, by Lemma 5.6 we have that $D_{AC}$ is strong,
biconnected and $\lambda(D_{AC})\leq k$.

Let us now prove that $\operatorname{\overrightarrow{\chi}}(D_{AC})\geq k+1$.
Suppose $D_{AC}$ admits a $k$-dicolouring $\varphi_{AC}$. Since $D_{B}$ is
$k$-extremal, $D_{B}-[a,b]$ admits a $k$-dicolouring $\varphi_{B}$ with
$\varphi_{B}(a)=\varphi_{B}(b)$. Up to permuting colours, we may assume that
$\varphi_{B}(a)=\varphi_{AC}(x)$. Let $\varphi:V(D)\to[1,k]$ be such that
$\varphi(y)=\varphi_{B}(y)$ if $y\in B$ and $\varphi(y)=\varphi_{AC}(y)$ if
$y\in A\cup C\setminus x$. As any dicycle of $D$ is either included in
$D_{B}$, or contains vertices that form a dicycle in $D/B=D_{AC}$, $\varphi$
is a $k$-dicolouring of $D$, a contradiction.

Thus
$k+1\leq\operatorname{\overrightarrow{\chi}}(D_{AC})\leq\lambda(D_{AC})+1\leq
k+1$. Hence
$\operatorname{\overrightarrow{\chi}}(D_{AC})=\lambda(D_{AC})=k+1$, which ends
the proof that $D_{AC}$ is $k$-extremal.

Suppose now that $D_{AC}$ and $D_{B}$ are $k$-extremal and let us prove that
$D$ is $k$-extremal.

Since $D_{AC}$ is $k$-extremal and is a Hajós bijoin of $D_{A}$ and $D_{C}$,
both $D_{A}$ and $D_{C}$ are $k$-extremal by Lemma 5.5.

Since $D_{BC}$ is the Hajós bijoin of $D_{B}$ and $D_{C}$ and $D_{B}$ and
$D_{C}$ are both $k$-extremal, $D_{BC}$ is biconnected, strong, Eulerian and
$\lambda(D_{BC})\leq k$ by Lemma 5.6. Finally, since $D$ is the Hajós bijoin
of $D_{A}$ and $D_{BC}$, by Lemma 5.6, $D$ is biconnected, strong, Eulerian
and $\lambda(D)\leq k$.

Let us now prove that $\operatorname{\overrightarrow{\chi}}(D)\geq k+1$.
Suppose that $D$ admits a $k$-dicolouring $\varphi_{D}$. Then, as
$D[B]=D_{B}-[a,b]$, and because $D_{B}$ is $k$-extremal,
$\varphi_{D}(a)=\varphi_{D}(b)$. We are going to split the proof into two
cases, in each case we prove that
$\operatorname{\overrightarrow{\chi}}(D_{AC})\leq k$, a contradiction.

Case 1: $\varphi_{D}(t)\neq\varphi_{D}(u)$

Since $\varphi_{D}(a)=\varphi_{D}(b)$, either
$\varphi_{D}(t)\neq\varphi_{D}(a)$ or $\varphi_{D}(u)\neq\varphi_{D}(b)$.
Suppose without loss of generality that $\varphi_{D}(t)\neq\varphi_{D}(a)$.
Let $\varphi_{C}$ be a $k$-dicolouring of $D_{C}-bu=D[C]+vb$ and, up to
permuting colours, assume that
$\varphi_{C}(b)=\varphi_{D}(b)(=\varphi_{D}(a))$. There is no monochromatic
$bv$-dipath with respect to $\varphi_{C}$ as $vb\in A(D_{C}-bu)$. Also,
$\varphi_{C}(b)=\varphi_{C}(u)$ for $D_{C}$ is $k$-extremal and thus
$k$-dicritical. Hence $\varphi_{C}(u)\neq\varphi_{D}(t)$.

Now, let $\varphi_{AC}:V(D_{AC})\to[1,k]$ be such that

$\varphi_{AC}(y)=\left\\{\begin{array}[]{ll}\varphi_{D}(a)&\text{ if }y=x\\\
\varphi_{C}(y)&\text{ if }y\in C\setminus b\\\ \varphi_{D}(y)&\text{ if }y\in
A\setminus a\end{array}\right.$

Observe that, since there is no monochromatic $bv$-dipath with respect to
$\varphi_{C}$, there is no monochromatic $xv$-dipath with respect to
$\varphi_{AC}$. Since any dicycle of $D_{AC}$ is either included in $A\cup x$
or in $C\cup x$, or goes through $tu$, or contains an $xv$-dipath,
$\varphi_{AC}$ is a $k$-dicolouring of $D_{AC}$, a contradiction.

Case 2: $\varphi_{D}(t)=\varphi_{D}(u)$.

There is not both a monochromatic $wt$-dipath and a monochromatic $uv$-dipath
with respect to $\varphi_{D}$. Without loss of generality, suppose there is no
monochromatic $uv$-dipath. Then, either there is no monochromatic $ub$-dipath
or no monochromatic $bv$-dipath. Suppose without loss of generality that there
is no monochromatic $bv$-dipath. Since $D_{A}$ is $k$-extremal, $D_{A}-aw$
admits a $k$-dicolouring $\varphi_{A}$. Up to permuting colours, we may assume
that $\varphi_{A}(a)=\varphi_{D}(a)$. Note that $ta\in A(D_{A}-aw)$, and thus
there is no monochromatic $at$-dipath in $\varphi_{A}(a)$.

Let $\varphi_{AC}:V(D_{AC})\to[1,k]$ be such that

$\varphi_{AC}(y)=\left\\{\begin{array}[]{ll}\varphi_{D}(a)&\text{ if }y=x\\\
\varphi_{A}(y)&\text{ if }y\in A\setminus a\\\ \varphi(y)&\text{ if }y\in
A\setminus a\end{array}\right.$

Observe that:

  * •

since there is no monochromatic $at$-dipath with respect to $\varphi_{A}$,
there is no monochromatic $xt$-dipath with respect to $\varphi_{AD}$,

  * •

since there is no monochromatic $uv$-dipath with respect to $\varphi_{D}$,
there is no monochromatic $uv$-dipath with respect to $\varphi_{AC}$, and

  * •

since there is no monochromatic $bv$-dipath with respect to $\varphi_{D}$,
there is no monochromatic $xv$-dipath with respect to $\varphi_{AD}$.

Finally, observe that dicycle of $D_{AC}$ is either included in $D_{AC}[A\cup
x]$ or $D_{AC}[C\cup x]$, or contains a $uv$-dipath, or a $xv$-dipath or a
$ww$-dipath. Hence, $\varphi_{AC}$ is a $k$-dicolouring of $D_{AC}$, a
contradiction.

This proves that $\operatorname{\overrightarrow{\chi}}(D)\geq k+1$. We now
have as usual $k+1\leq\operatorname{\overrightarrow{\chi}}(D)\lambda(D)+1\leq
k+1$, so $\operatorname{\overrightarrow{\chi}}(D)=\lambda(D)+1=k+1$, and since
we already proved that $D$ is strong and biconnected, we get that $D$ is
$k$-extremal.

∎

The algorithm will use the following third decomposition theorem for
$\vec{\mathcal{H}}_{k}$. Recall that Hajós star join is a Hajós tree join in
which the tree is a star. See Figure 9.

######  Theorem 7.3.

Let $k\geq 3$. If $D$ is $k$-extremal, then one of the following holds:

  * •

either $D=\overleftrightarrow{K}_{k}$,

  * •

or $D$ is a symmetric odd wheel (only in the case $k=3$),

  * •

or $D$ is a directed Hajós join,

  * •

or $D$ is a parallel Hajós join,

  * •

or $D$ is a Hajós star join.

$x$$v_{1}$$x$$v_{2}$$x$$v_{3}$$D$$x$$v_{1}$$x$$v_{2}$$x$$v_{3}$ Figure 9: $D$
is a Hajós star join of three digraphs.

###### Proof.

Suppose $D\neq\overleftrightarrow{K}_{k}$ and $D$ is not a symmetric odd
wheel. By Theorem 6.8, $D\in\vec{\mathcal{H}}_{k}$. Since it is one of the
possible outputs of this theorem, we can assume that $D$ is not a directed
Hajós join. Thus $D$ is a Hajós tree join: there exists a tree $T$ with edges
$\\{u_{1}v_{1},\dots,u_{n}v_{n}\\}$, some digraphs $D_{1},\dots,D_{n}$ with
$[u_{i},v_{i}]\subseteq A(D_{i})$ for $i=1,\dots,n$ such that
$D=T(D_{1},\dots,D_{n};C)$, where $C$ is the peripheral cycle.

If $T$ is a star, then $D$ is a Hajós star join of $D_{1},\dots,D_{n}$ and we
are done.

Hence, there is $u_{i},v_{i}\in E(T)$ such that $u_{i}$ and $v_{i}$ are both
interior vertices of $T$. Let $T_{u_{i}}$ and $T_{v_{i}}$ be the two connected
component of $T-u_{i}v_{i}$ containing respectively $u_{i}$ and $v_{i}$. Since
$C$ goes through each leaves of $T$ following the natural ordering of an
embedding of $T$, $C$ is the concatenation of two vertex disjoint dipaths
$P_{u_{i}}$ and $P_{v_{i}}$ such that $V(P_{u_{i}})$ are the leaves of $T$
contained in $T_{u_{i}}$ and $V(P_{v_{i}})$ are the leaves of $T$ contained in
$T_{v_{i}}$. There is $x_{u_{i}},y_{v_{i}}\in V(P_{u_{i}})$ and
$x_{v_{i}},y_{v_{i}}\in V(P_{v_{i}})$ such that
$x_{u_{i}}y_{v_{i}},x_{v_{i}}y_{u_{i}}\in A(C)$.

Let $D^{\prime}$ be the digraph obtained from $D$ by deleting
$V(D_{i})\setminus\\{u_{i},v_{i}\\}$ and identifying $u_{i}$ and $v_{i}$ to a
new vertex $x$. Then $D$ is the Hajós parallel join of $D^{\prime}$ and
$D_{ab}$ with respect to $(x_{u_{i}},y_{v_{i}},x_{v_{i}},y_{u_{i}})$. To see
this, look at Definition 7.1 and observe that:

  * •

$D_{i}$ plays the role of $D_{B}$,

  * •

$D^{\prime}$ plays the role of $D_{AC}$,

  * •

$A=\bigcup_{u_{j}v_{j}\in T_{u_{i}}}V(D_{j})$ and $C=\cup_{u_{j}v_{j}\in
T_{v_{i}}}V(D_{j})$,

  * •

$x_{u_{i}},y_{v_{i}},x_{v_{i}},y_{u_{i}}$ plays the role of respectively
$t,u,v,w$

Finally, observe that $x_{u_{i}},y_{u_{i}}$ are in the same connected
component of $D[A]\setminus x$ because of $P_{u_{i}}$ and
$x_{v_{i}},y_{v_{i}}$ are in the same connected component of $D[C]\setminus x$
because of $P_{v_{i}}$.

∎

######  Theorem 7.4.

Let $k\geq 3$. There is an algorithm that decides if a given digraph $D$ is
$k$-extremal in time $\mathcal{O}(n^{10})$.

###### Proof.

Our algorithm is based on Theorem 7.3 together with Lemmata 5.3, 7.2 and 6.7

Let $D$ be a digraph on $n$ vertices. Checking if $D$ is strong and
biconnected can be done in time $\mathcal{O}(n^{2})$. It takes time
$\mathcal{O}(n^{2})$ to check if $D=\overleftrightarrow{K}_{k}$ or $D$ is a
symmetric odd wheel. If $D=\overleftrightarrow{K}_{k}$, then our algorithm
outputs that $D$ is $k$-extremal. We may now assume that $D$ is strong,
biconnected and distinct from $\overleftrightarrow{K}_{k}$ and symmetric odd
wheels.

######  Claim 7.4.1.

We can decide in time $\mathcal{O}(n^{5})$ that either $D$ is not the directed
Hajós join of two digraphs, or $D$ is the directed Hajós join of two digraphs
$D_{1}$ and $D_{2}$ and compute $D_{1}$ and $D_{2}$.

Proof of Claim : Checking if $D$ is a directed Hajós join of two digraphs
$D_{1}$ and $D_{2}$ can be done by testing for all triples of vertices
$(u,v,w)$ if $uw\in A(D)$, $D\setminus v-uw$ is not connected and $u$ and $w$
are in distinct components of $D\setminus v-uw$. If $(u,v,w)$ is such a
triple, Let $R_{u}$ (resp. $R_{w}$) be the connected component of $D\setminus
v-uw$ containing $u$ (resp. containing $w$).Then $D$ is the directed Hajós
join of $D[R_{u}\cup v]+uv$ and $D[R_{w}\cup v]+vw$. This can be done in time
$\mathcal{O}(n^{5})$. $\square$

######  Claim 7.4.2.

We can decide in time $\mathcal{O}(n^{8})$ that either $D$ is not the parallel
Hajós join of two digraphs, or $D$ is the parallel Hajós join of two digraphs
$D_{1}$ and $D_{2}$ and compute $D_{1}$ and $D_{2}$.

Proof of Claim : Checking if $D$ is a directed Hajós join of two digraphs
$D_{1}$ and $D_{2}$ can be done by testing for all $6$-tuples of vertices
$(t,u,v,w,a,b)$ if $tu,vw\in A(D)$, $D\setminus\\{a,b\\}-\\{tu,vw\\}$ has a
connected component $A$ containing both $t$ and $u$, a connected component $C$
containing both $u$ and $v$, and some other connected components union of
which we name $B$. Then $D$ is the parallel Hajós join of the digraphs
obtained from $D[A\cup a]$ and $D[C\cup b]$ by deleting $tu,vw$, identifying
$a$ and $b$ into a new vertex $x$, and adding arcs $tx,xw,vx,xu$, and
$D[B]+[a,b]$. This can be done in time $\mathcal{O}(n^{8})$.

$\square$

######  Claim 7.4.3.

We can decide in time $\mathcal{O}(n^{5})$ that either $D$ is not the Hajós
star join of some digraphs, or $D$ is a Hajós star join of some digraphs
$D_{1},\dots,D_{\ell}$ and compute $D_{1},\dots,D_{\ell}$.

Proof of Claim : Observe that $D$ is a Hajós star join of $\ell$ digraphs if
and only if it has $\ell+1$ vertices $x,v_{1},\dots,v_{\ell}$ such that
$C=v_{1}\rightarrow\dots\rightarrow v_{\ell}\rightarrow v_{1}$ and $D\setminus
x-A(C)$ has exactly $\ell$ connected component $R_{1},\dots,R_{\ell}$ such
that $v_{i}\in R_{i}$ for $i=1,\dots,\ell$. Indeed, if it is the case then
$D=T(D_{1},\dots,D_{\ell},C)$ where $T$ is the tree with edges
$\\{xv_{1},\dots,xv_{\ell}\\}$, and $D_{i}=D[R_{i}\cup x]+[x,v_{i}]$, and the
"only if" part is straightforward by definition of a Hajós star join.

Hence, given $\ell+1$ vertices $y,p_{1},\dots,p_{\ell}$, we can decide if they
can play the role of respectively $x,v_{1},\dots,v_{\ell}$ in time
$\mathcal{O}(n^{2})$. But this is not enough to conclude because $\ell$ can be
large.

Anyway, we are going to show that given a triple of vertices
$(y,p_{\ell},p_{1})$, we can guess in time $\mathcal{O}(n^{2})$ if there
exists $p_{2},\dots,p_{\ell-1}$ such that $y,p_{1},\dots,p_{\ell}$ can play
the role of respectively $x,v_{1},\dots,v_{\ell}$. In this case, we say that
$(y,p_{\ell},p_{1})$ is a good guess.

Let $(y,p_{\ell},p_{1})$ be a triple of vertices of $D$ such that
$p_{\ell}p_{1}\in A(G)$. Compute the list of bridges $\mathcal{B}$ of
$D\setminus y-p_{\ell}p_{1}$. This can be done in $\mathcal{O}(n^{2})$ time.
Observe that if $\mathcal{B}$ does not contain a $p_{1}p_{\ell}$-dipath, then
our guess is wrong. Assume otherwise, and observe that $\mathcal{B}$ induces a
forest, so it has a unique $p_{1}p_{\ell}$-dipath, say $P=p_{1}\rightarrow
p_{2}\rightarrow\dots\rightarrow p_{\ell}$. Now, $(y,p_{\ell},p_{1})$ is a
good guess if and only $p_{2},p_{3},\dots,p_{\ell-1}$ can play the role of
respectively $v_{2},\dots,v_{\ell-1}$, so we are done.

Altogether, it takes $\mathcal{O}(n^{2})$ to decide if a triple of vertices is
a good guess, so the total time is $\mathcal{O}(n^{5})$.

$\square$

Thus in time $\mathcal{O}(n^{8})$, we can check whether $D$ is a directed
Hajós join or a parallel Hajós join of two digraphs $D_{1}$ and $D_{2}$ and
compute $D_{1}$ and $D_{2}$, or a Hajós star join of $\ell$ digraphs
$D_{1},\dots D_{\ell}$ and compute $D_{1},\dots,D_{\ell}$. If all these checks
fail, then by Theorem 7.3 $D$ is not $k$-extremal.

If $D$ is a directed Hajós join of two digraphs $D_{1}$ and $D_{2}$, we can
then recursively check whether $D_{1}$ and $D_{2}$ are $k$-extremal, and our
algorithm can return that $D$ is $k$-extremal if and only if they both are
$k$-extremal, by Lemma 5.3. We do the same if $D$ is a parallel join (Lemma
7.2) or a star Hajós join (Lemma 6.7).

Let us now prove that our algorithm has time complexity $\mathcal{O}(n^{10})$.
First, note that in each case, in time $\mathcal{O}(n^{8})$, either we
conclude that $D$ is not $k$-extremal, or we make $\ell\geq 2$ recursive calls
on digraphs $(D_{i})_{i\in[1,\ell]}$. We have that
$\sum_{i\in[1,\ell]}|V(D_{i})|-1\leq|V(D)|-1$ and for $i\in[1,\ell]$, that
$2\leq|V(D_{i})|<|V(D)|$. Let us consider $T$, the rooted tree of recursive
calls of our algorithm, with each node $v$ labelled with the digraph $D_{v}$
of the corresponding recursive call. Let $depth$ be the function which
associates to a node its depth in $T$. Then,

$\sum_{v\mid depth(v)=0}|V(D_{v})|-1=V(D)-1\leq n$

and, for $i\geq 1$,

$\sum_{v\mid depth(v)\leq i}|V(D_{v})|-1\leq\sum_{v\mid
depth(v)=i-1}|V(D_{v})|-1.$

Thus we can recursively prove for any $k\in\mathbb{N}$ that $\sum_{v\mid
depth(v)\leq k}|V(D_{v})|-1\leq n$. As every $D_{v}$ has $|V(D_{v})|\geq 2$,
this implies that there are at most $n$ calls at any depth. But, since $T$ has
depth at most $n$, this means there are at most $n^{2}$ recursive calls. Each
of these recursive calls takes time at most $\mathcal{O}(n^{8})$, and thus our
algorithm has time complexity $\mathcal{O}(n^{10})$. ∎

##  8 The hypergraph case

As mentioned in the introduction, Theorem 1.2 has already been generalized to
hypergraph with chromatic number at least $4$ by Schweser, Stiebitz and Toft
[30]. Their result is closely related to ours as we explain below.

Let $H$ be a hypergraph. Its chromatic number $\chi(H)$ is the least integer
$k$ such that the vertices of $H$ can be coloured in such a way that no
hyperedge is monochromatic. A $uv$-hyperpath in $H$ is a sequence
$(u_{1},e_{1},u_{2},e_{2},\dots,e_{q-1},u_{q})$ of distinct vertices
$u_{1},u_{2},\dots,u_{q}$ of $H$ and distinct hyperedges
$e_{1},e_{2},\dots,e_{q-1}$ of $H$ such that $u=u_{1},v=u_{q}$ and
$\\{u_{i},u_{i+1}\\}\subseteq e_{i}$ for $i\in\\{1,2,\dots,q-1\\}$. The local
connectivity $\lambda(u,v)$ of two vertices $u$ and $v$ is the maximum number
of hyperedge-disjoint $uv$-hyperpaths linking $u$ and $v$ and the maximum
local connectivity of $H$ is $\lambda(H)=max_{u\neq v}\lambda(u,v)$.

Let $H_{1}$ and $H_{2}$ be two hypergraphs and, for $i=1,2$, let $e_{i}\in
E(H_{i})$ and $v_{i}\in e_{i}$. The Hajós hyperjoin of $H_{1}$ and $H_{2}$
with respect to $((e_{1},v_{1}),(e_{2},v_{2}))$ is the hypergraph $H$ obtained
from $H_{1}$ and $H_{2}$ by identifying $v_{1}$ and $v_{2}$ into a new vertex
$v$, deleting $e_{1}$ and $e_{2}$ and adding a new edge $e$ where $e=e_{1}\cup
e_{2}\setminus\\{v_{1},v_{2}\\}$ or $e=e_{1}\cup
e_{2}\cup\\{v\\}\setminus\\{v_{1},v_{2}\\}$.

Let $\mathcal{H}_{3}$ be the smallest class of hypergraphs that contains all
odd wheels and is closed under taking Hajós hyperjoins, and for $k\geq 4$,
$\mathcal{H}_{k}$ is the smallest class of hypergraphs that contains $K_{k+1}$
and is closed under taking Hajós hyperjoins. We do not define precisely here
what a block for an hypergraph is - it is the natural extension of the one for
a graph - we refer the reader to [30] for a rigorous definition.

######  Theorem 8.1 ([30]).

Let $H$ be a hypergraph with $\chi(H)=k+1\geq 4$. Then $\chi(H)=\lambda(H)+1$
if and only if a block of $H$ is in $\mathcal{H}_{k}$.

Given a digraph $D$, let $H_{D}$ be the hypergraph on vertex set $V(D)$, and
$e\subseteq V(D)$ is a hyperedge of $H_{D}$ if and only if it induces a
directed cycle in $D$. We clearly have that
$\operatorname{\overrightarrow{\chi}}(D)=\chi(H_{D})$. Hence, one could
suspect that our result is actually implied by the result of Schweser,
Stiebitz and Toft. But this is not the case because a dipath of $D$ does not
need to translate into a hyperpath of $H_{D}$, and thus the maximum local arc-
connectivity of $D$ does not need to be equal to the maximum local edge-
connectivity of $H_{D}$. Actually, we can prove that the class of extremal
digraphs contains the class of extremal hypergraph in the following sense:

######  Lemma 8.2.

Let $k\geq 3$. For every hypergraph $H\in\mathcal{H}_{k}$, there exists a
digraph $D\in\vec{\mathcal{H}}_{k}$ such that $H_{D}=H$.

The above lemma is a direct consequence of the following property of
hypergraphs in $\mathcal{H}_{k}$.

######  Property 8.3.

Let $H\in\mathcal{H}_{k}$. Then for every $e,e^{\prime}\in E(H)$, $|e\cap
e^{\prime}|\leq 1$.

cbad Figure 10: A $3$-extremal digraph. The two induced dicycles $a\rightarrow
b\rightarrow c\rightarrow a$ and $a\rightarrow d\rightarrow c\rightarrow a$
share two vertices. Hence its hypergraph of induced dicycles is not
$3$-extremal.

###### Proof.

The result holds for complete graphs and odd wheels, and it is easy to see
that if it holds for two hypergraphs $H_{1}$ and $H_{2}$, then it also holds
for any Hajós hyperjoin of $H_{1}$ and $H_{2}$. ∎

###### of Lemma 8.2.

Using directed Hajós join, it is easy to construct a digraph
$D\in\vec{\mathcal{H}}_{k}$ that has two induced directed cycles with two
common vertices, see Figure 10 for an example. By Property 8.3,
$H_{D}\notin\mathcal{H}_{k}$. ∎

We actually believe that the class of extremal digraphs strictly contains the
class of extremal hypergraph, but we were not able to prove the following that
there exist (an infinite family of) digraphs $D$ such that
$D\in\vec{\mathcal{H}}_{k}$ and $H_{D}\notin\mathcal{H}_{k}$.

##  9 $2$-extremal digraphs

Similarly to hypergraphs, the $2$-extremal digraphs seems to be more difficult
to characterize. $\overleftrightarrow{K}_{3}$, and more generally symmetric
odd cycles are of course $2$-extremal.

$c$$e$$a$$b$$e$$g$$e$$h$$g$$i$$g$$d$$h$$j$$D$ Figure 11: A $2$-extremal
digraphs

######  Definition 9.1 (2-Hajós tree join).

Given

  * •

a tree $T$ embedded in the plane with at least two edges,

  * •

A partition $(A,B)$ of the edges of $T$, with
$A=\\{u_{1}v_{1},\dots,u_{a}v_{a}\\}$ and
$B=\\{x_{1}y_{1},\dots,x_{b}y_{b}\\}$ such that every leaf to leaf path in $T$
contains an even number of edges of $B$,

  * •

a circular ordering $C=(x_{1},\dots,x_{\ell})$ of the leaves of $T$, taken
following the natural ordering given by the embedding of $T$, and

  * •

for $i=1,\dots,a$, a digraph $D_{i}$ such that

    * –

$V(D_{i})\cap V(T)=\\{u_{i},v_{i}\\}$,

    * –

$[u_{i},v_{i}]\subseteq A(D_{i})$, and

    * –

for $1\leq i\neq j\leq a$, $V(D_{i})\setminus\\{u_{i},v_{i}\\}\cap
V(D_{j})\setminus\\{u_{j},v_{j}\\}=\emptyset$,

we define the 2-Hajós tree join $T(D_{1},\dots,D_{a};C)$ to be the digraph
obtained from $T$ by replacing each edge $u_{i}v_{i}\in A$ by
$D_{i}-[u_{i},v_{i}]$, each edge $x_{i}y_{i}\in B$ by a digon and by adding
the directed cycle $C=x_{1}\rightarrow x_{2}\rightarrow\dots\rightarrow
x_{\ell}\rightarrow x_{1}$.

Observe that, in the definition of $2$-Hajós tree joins, if $A=\emptyset$,
then the resulting digraphs is a generalised wheel.

Let $\mathcal{H}_{2}$ be the smallest class of digraphs containing symmetric
odd cycle and closed under taking directed Hajós join and $2$-Hajós tree join.
It is a routine work to check that digraphs in $\mathcal{H}_{2}$ are
$2$-extremal. We conjecture that they are the only ones.

######  Conjecture 9.2.

A digraph is $2$-extremal if and only if it is in $\mathcal{H}_{2}$.

#### Acknowledgement

This research was partially supported by the ANR project DAGDigDec (JCJC)
ANR-21-CE48-0012 and by the group Casino/ENS Chair on Algorithmics and Machine
Learning.

## References

  * [1] Pierre Aboulker and Guillaume Aubian.  Four proofs of the directed brooks’ theorem.  Discrete Mathematics, page 113193, 2022.
  * [2] Pierre Aboulker, Guillaume Aubian, and Pierre Charbit.  Decomposing and colouring some locally semicomplete digraphs.  Eur. J. Comb., 106:103591, 2022.
  * [3] J. Bang-Jensen, T. Bellitto, T. Schweser, and M. Stiebitz.  Hajós and ore constructions for digraphs.  Electronic Journal of Combinatorics, 27(1):1–63, 2020.
  * [4] Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, and Nicolas Trotignon.  Coloring graphs with constraints on connectivity.  J. Graph Theory, 85(4):814–838, 2017.
  * [5] Pierre Aboulker, Pierre Charbit, and Reza Naserasr.  Extension of Gyárfás-Sumner conjecture to digraphs.  The Electronic Journal of Combinatorics, 28(2), May 2021.
  * [6] Pierre Aboulker, Nathann Cohen, Fréderic Havet, William Lochet, Phablo Moura, and Stéphan Thomassé.  Subdivisions in digraphs of large out-degree or large dichromatic number.  The Electronic Journal of Combinatorics, 26(3), 10 2016.
  * [7] P. Aboulker, F. Havet, K. Knauer, and C. Rambaud.  On the dichromatic number of surfaces.  Accepted to Eurocomb 2021, 2021.
  * [8] Julien Bensmail, Ararat Harutyunyan, and Ngoc Khang Le.  List coloring digraphs.  Journal of Graph Theory, 87(4):492–508, April 2018.
  * [9] Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé.  Tournaments and colouring.  Journal of Combinatorial Theory, Series B, 103:1–20, 01 2013.
  * [10] R. L. Brooks.  On colouring the nodes of a network.  Math. Proc. Cambridge Philos. Soc., 37:194–197, 1941.
  * [11] L. Gishboliner, R. Steiner, and T. Szabo.  Dichromatic number and forced subdivisions.  Submitted, 2020.
  * [12] György Hajós.  Uber eine konstruktion nicht n-farbbarer graphen.  Martin-Luther-Univ, Halle-Wittenberg, 1961.
  * [13] A. Harutyunyan and B. Mohar.  Strengthened brooks theorem for digraphs of girth three.  The Electronic Journal of Combinatorics, 18(1):170–180, 2011.
  * [14] Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos.  Digraph coloring and distance to acyclicity.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 41:1–41:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [15] Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, and Stéphan Thomassé.  Coloring dense digraphs.  Electronic Notes in Discrete Mathematics, 61(5):577–583, 2017.  The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17).
  * [16] Ararat Harutyunyan and Bojan Mohar.  Two results on the digraph chromatic number.  Discrete Mathematics, 312(10):1823–1826, 2012.
  * [17] Winfried Hochstättler.  A flow theory for the dichromatic number.  European Journal of Combinatorics, 66:160–167, 2017.  Selected papers of EuroComb15.
  * [18] Richard Hoshino and Ken ichi Kawarabayashi.  The edge density of critical digraphs.  Combinatorica, 35:619–631, 2015.
  * [19] K. Knauer and P. Valicov.  Cuts in matchings of 3-connected cubic graphs.  European Journal of Combinatorics, 76:27–36, 2019.
  * [20] Alexandr Kostochka and Michael Stiebitz.  The minimum number of edges in 4-critical digraphs of given order.  Graphs and Combinatorics, 36, 05 2020.
  * [21] Zhentao Li and Bojan Mohar.  Planar digraphs of digirth four are 2-colorable.  SIAM Journal on Discrete Mathematics, 31, 06 2016.
  * [22] L. Lovász.  On decomposition of graphs.  Studia Sci. Math. Hungar, 1:237–238, 1966.
  * [23] L Lovász.  Connectivity in digraphs.  Journal of Combinatorial Theory, Series B, 15(2):174–177, 1973\.
  * [24] W. Mader.  Grad und lokaler zusammenhang in endlichen graphen.  Math. Ann., 205(1):9–11, 1973.
  * [25] Karl Menger.  Zur allgemeinen kurventheorie.  Fund. Math., 10:96–115, 1927.
  * [26] B. Mohar.  circular colourings of edge-weighted graphs.  Journal of Graph Theory, 43:107–116, 2003.
  * [27] B. Mohar.  Eigenvalues and colourings of digraphs.  Linear Algebra and its Applications, 432(9):2273–2277, 2010.
  * [28] V Neumann-Lara.  The dichromatic number of a digraph.  Journal of Combinatorial Theory, Series B, 33(3):265–270, 1982\.
  * [29] L. Rabern.  A different short proof of brooks’ theorem.  Discussiones Mathematicae Graph Theory, 34(3):633–634, 2014.
  * [30] Thomas Schweser, Michael Stiebitz, and Bjarne Toft.  Coloring hypergraphs of low connectivity, 2018.
  * [31] R. Steiner.  A note on graphs of dichromatic number 2.  Submited, 2019.
  * [32] R. Steiner.  A note on colouring digraphs of large girth.  Discrete Applied Mathematics, 287:62–64, 2020.
  * [33] Raphael Steiner.  On coloring digraphs with forbidden induced subgraphs.  ArXiv, abs/2103.04191, 2021.
  * [34] Michael Stiebitz and Bjarne Toft.  A brooks type theorem for the maximum local edge connectivity.  Electronic Journal of Combinatorics, 25, 03 2016.