---
abstract: 'The chromatic number ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)$ of a digraph $D$ is the minimum number of colors needed to color the vertices of $D$ such that each color class induces an acyclic subdigraph of $D$. A digraph $D$ is $k$-critical if ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) = k$ but ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D'') < k$ for all proper subdigraphs $D''$ of $D$. We examine methods for creating infinite families of critical digraphs, the *Dirac join* and the directed and bidirected *Hajós join*. We prove that a digraph $D$ has chromatic number at least $k$ if and only if it contains a subdigraph that can be obtained from bidirected complete graphs on $k$ vertices by (directed) Hajós joins and identifying non-adjacent vertices. Building upon that, we show that a digraph $D$ has chromatic number at least $k$ if and only if it can be constructed from bidirected $K_k$’s by using directed and bidirected Hajós joins and identifying non-adjacent vertices (so called Ore joins), thereby transferring a well-known result of Urquhart to digraphs. Finally, we prove a Gallai-type theorem that characterizes the structure of the low vertex subdigraph of a critical digraph, that is, the subdigraph, which is induced by the vertices that have in-degree $k-1$ and out-degree $k-1$ in $D$.'
author:
- '[[J[ø]{}rgen Bang-Jensen]{}[^1] [^2]]{}'
- '[[Thomas Bellitto]{}[^3]]{}'
- '[[Thomas Schweser]{}[^4]]{}'
- '[[Michael Stiebitz]{}[^5]]{}'
title: '**Hajós and Ore constructions for digraphs**'
---

[ 05C20 ]{}

[ Digraph coloring, Critical digraphs, Hajós join, Ore join]{}

Introduction
============

Recall that the **chromatic number** $\chi(G)$ of a graph $G$ is the minimum number of colors needed to color the vertices of $G$ so that each color class induces an edgeless subgraph of $G$. A graph $G$ is $k$-critical if $\chi(G)=k$ but $\chi(G') < k$ for each proper subgraph $G'$ of $G$. The topic of critical graphs has received much attention within the last century. Critical graphs were first introduced by G. A. Dirac in his doctoral thesis; famous mathematicians like G Hajós, T. Gallai and others continued developing the theory of critical graphs in the 1960’s.

However, not much is known regarding critical digraphs. Following Neumann-Lara [@NeuLa82], the chromatic number ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)$ of a digraph $D$ is the minimum number of colors needed to color the vertices of $D$ so that each color class induces an acyclic subdigraph of $D$, *i.e.*, a subdigraph that does not contain any directed cycles. A digraph $D$ is $k$**-critical** (or, briefly, **critical**) if ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)=k$ but ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D')<k$ for each proper subdigraph of $D$. Let $\text{Crit}(k)$ denote the class of $k$-critical digraphs. Then, it is easy to see that $\text{Crit}(0)=\{\varnothing\}, \text{ Crit}(1)=\{K_1\}$, and that $\text{Crit}(2)$ consists of all directed cycles. Nevertheless, it is not even known which digraphs $\text{Crit}(3)$ consists of; unlike in the undirected case, where it follows from König’s characterization of bipartite graphs that $\text{Crit}(3)$ coincides with the class of all odd cycles. In this paper, we study the digraph analogue of two well-known methods for creating infinite families of critical graphs, the so-called *Dirac join* and the *Hajós join*. Moreover, we prove that a digraph $D$ has chromatic number at least $k$ if and only if it contains a Hajós-$k$-constructible subdigraph, that is, a subdigraph of $D$ that can be obtained from bidirected $K_k$’s by iteratively applying the Hajós join and identifying non-adjacent vertices (see Theorem \[theorem\_Hajos-constructible\]). In Section \[section\_gallai\] we prove a Gallai-type theorem that characterizes the structure of the low-vertex subdigraph of a $k$-critical digraph, that is, the subdigraph that is induced by the vertices having in-degree and out-degree $k-1$.

Basic Terminology
=================

Most of our terminology is defined as in [@BaGu08]. Let $D=(V(D),A(D))$ be a digraph. Then, $V(D)$ is the **set of vertices** of $D$ and $A(D)$ is the **set of arcs** of $D$. The order $|D|$ of $D$ is the size of $V(D)$. Digraphs in this paper are not allowed to have loops nor parallel arcs; however, there may be two arcs in opposite directions between two vertices (in this case we say that the arcs are **opposite**). We denote by $uv$ the arc whose **initial vertex** is $u$ and whose **terminal vertex** is $v$. Two vertices $u,v$ are **adjacent** if at least one of $uv$ and $vu$ belongs to $A(D)$. If $u$ and $v$ are adjacent, we also say that $u$ is a **neighbor** of $v$ and vice versa. If $uv \in A(D)$, then $v$ is called an **out-neighbor** of $u$ and $u$ is called an **in-neighbor** of $v$. By $N_D^+(v)$ we denote the set of out-neighbors of $v$; by $N_D^-(v)$ the set of in-neighbors of $v$. Given a digraph $D$ and a vertex set $X$, by $D[X]$ we denote the subdigraph of $D$ that is **induced** by the vertex set $X$, that is, $V(D[X])=X$ and $A(D[X])=\{uv \in A(D) ~|~ u,v \in X\}$. A digraph $D'$ is said to be an induced subdigraph of $D$ if $D'=D[V(D')]$. As usual, if $X$ is a subset of $V(D)$, we define $D-X=D[V(D) \setminus X]$. If $X=\{v\}$ is a singleton, we use $D-v$ rather than $D- \{v\}$. The **out-degree** of a vertex $v \in V(D)$ is the number of arcs whose inital vertex is $v$; we denote it by $d_D^+(v)$. Similarly, the number of arcs whose terminal vertex is $v$ is called the **in-degree** of $v$ and is denoted by $d_D^-(v)$. Note that $d_D^+(v)=|N_D^+(v)|$ and $d_D^-(v)=|N_D^-(v)|$ for all $v \in V(D)$. A vertex $v \in V(D)$ is **Eulerian** if $d_D^+(v)=d_D^-(v)$. Moreover, the digraph $D$ is **Eulerian** if every vertex of $D$ is Eulerian.

Given a digraph $D$, its **complement** is the digraph $\overline{D}$ with $V(\overline{D})=V(D)$ and $A(\overline{D})=\{uv ~|~ u,v \in V(D) \text{ and } uv \not \in A(D)\}$. The **underlying** graph $G(D)$ of $D$ is the simple undirected graph with $V(G(D))=V(D)$ and $\{u,v\}\in E(G(D))$ if and only if at least one of $uv$ and $vu$ belongs to $A(D)$. The digraph $D$ is **(weakly) connected** if $G(D)$ is connected. A **separating vertex** of a connected digraph $D$ is a vertex $v \in V(D)$ such that $D-v$ is not connected. Furthermore, a **block** of $D$ is a maximal subdigraph $D'$ of $D$ such that $D'$ has no separating vertex.

A **directed path** is a non-empty digraph $P$ with $V(P)=\{v_1,v_2,\ldots,v_p\}$ and $A(P)=\{v_1v_2, v_2v_3, \ldots, v_{p-1}v_p\}$ where the $v_i$ are all distinct. Furthermore, a **directed cycle** of **length** $p\geq 2$ is a non-empty digraph $C$ with $V(C)=\{v_1,v_2,\ldots,v_p\}$ and $A(C)=\{v_1v_2,v_2v_3, \ldots, v_{p-1}v_p, v_pv_1\}$ where the $v_i$ are all distinct. A directed cycle of length $2$ is called a **digon**. A **bidirected** graph is a digraph that can be obtained from an undirected (simple) graph $G$ by replacing each edge by two opposite arcs, we denote it by $D(G)$. A bidirected complete graph is also called a **complete digraph**. By ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ we denote the bidirected complete graph on $k$ vertices. It is easy to see that ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D(G))=\chi(G)$ and $D(G)$ is critical with respect to ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}$ if and only if $G$ is critical with respect to $\chi$.

Construction of critical digraphs {#section_construction}
=================================

Let $D_1$ and $D_2$ be two disjoint digraphs. Let $D$ be the digraph obtained from the union $D_1 \cup D_2$ by adding all possible arcs in both directions between $D_1$ and $D_2$, *i.e.*, $V(D)=V(D_1) \cup V(D_2)$ and $A(D)=A(D_1) \cup A(D_2) \cup \{uv, vu ~|~ u \in V(D_1) \text{ and } v \in V(D_2)\}$. We say that $D$ is the **Dirac join** of $G_1$ and $G_2$ and denote it by $D= D_1 \boxplus D_2$. The proof of the next theorem is straightforward and therefore left to the reader.

Let $D=D_1 \boxplus D_2$ be the Dirac join of two disjoint non-empty digraphs $D_1$ and $D_2$. Then, ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) = {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1) + {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2)$ and $D$ is critical if and only if both $D_1$ and $D_2$ are critical.

The Hajós join is a well-known tool for undirected graphs that can be used to create infinite families of $k$-critical graphs, see e. g. [@Ha61]. For digraphs, an equivalent construction was defined by Hoshino and Kawarabayashi in [@HoKa14]. Let $D_1$ and $D_2$ be two disjoint digraphs and select an arc $u_1v_1$ and an arc $v_2u_2$. Let $D$ be the digraph obtained from the union $D_1 \cup D_2$ by deleting the arcs $u_1v_1$ as well as $v_2u_2$, identifying the vertices $v_1$ and $v_2$ to a new vertex $v$, and adding the arc $u_1u_2$. We say that $D$ is the **(directed) Hajós join** of $D_1$ and $D_2$ and write $D=(D_1,v_1,u_1) \triangledown (D_2,v_2,u_2)$ or, briefly, $D=D_1 \triangledown D_2$. For the proof of the next theorem, recall that a $k$-coloring of a digraph $D$ is a coloring of $D$, in which at most $k$ colors are used. Statement (c) of the following theorem has already been mentioned in [@HoKa14 Prop. 2]

\[theorem\_Hajos-join\] Let $D=D_1 \triangledown D_2$ be the Hajós join of two disjoint non-empty digraphs $D_1$ and $D_2$. Then, the following statements hold:

-   ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) \geq \min\{{\overset{\text{\tiny$\bm\rightarrow$}}{\chi}} (D_1), {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2)\}$.

-   If ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1)={\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2)=k$ and $k \geq 3$, then ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)=k$.

-   If both $D_1$ and $D_2$ are $k$-critical and $k \geq 3$, then $D$ is $k$-critical.

-   If $D$ is $k$-critical and $k \geq 3$, then both $D_1$ and $D_2$ are $k$-critical.

Suppose that $D=(D_1,v_1,u_1) \triangledown (D_2,v_2,u_2)$ and let $v$ denote the vertex that is obtained from identifying $v_1$ and $v_2$. For the proof of (a) let ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)=k$ and let $\varphi$ be a $k$-coloring of $D$. For $i \in \{1,2\}$, let $\varphi_i$ denote the restriction of $\varphi$ to $D_i$, where $\varphi_i(v_i)=\varphi(v).$ We claim that either $\varphi_1$ is a $k$-coloring of $D_1$ or $\varphi_2$ is a $k$-coloring of $D_2$. Otherwise, in $D_1$ there is a monochromatic directed cycle $C_1$ that contains the arc $u_1v_1$ (as $D_1 - u_1v_1$ is a subdigraph of $D$ and therefore $k$-colorable). Similar, in $D_2$ there exists a monochromatic cycle $C_2$ that contains the arc $v_2u_2$. But then, $C_1 \cup C_2 - u_1v_1 - v_2u_2 + u_1u_2$ is a monochromatic directed cycle in $D$, a contradiction. This proves (a).

In order to prove (b), let ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1)={\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2)=k$. By (a), ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) \geq k$. Thus, it suffices to show that ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) \leq k$. For $i \in \{1,2\}$, let $\varphi_i$ be a $k$-coloring of $D_i$. By permuting the colors if necessary we obtain $\varphi_1(v_1)=\varphi_2(v_2)$. For $w \in V(D)$ let $$\varphi(w) =
\begin{cases}
\varphi_1(w) \quad \text{if } w \in V(D_1),\\
\varphi_2(w) \quad \text{if } w \in V(D_2), \text{ and  }\\
\varphi_1(v_1) \quad \text{if } w=v.
\end{cases}$$ We claim that $\varphi$ is a $k$-coloring of $D$. For otherwise, $D$ would contain a monochromatic directed cycle $C$ with $\{u_1,u_2,v\} \subseteq V(C)$ and $u_1u_2 \in A(C)$. But then, $(C \cap D_1) + u_1v_1$ is a monochromatic directed cycle in $D_1$, which is impossible.

For the proof of (c) it suffices to show that ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D-a) < k$ for all $a \in A(D)$ (by (b)). If $a = u_1u_2$, then choosing $(k-1)$-colorings of $D_1 - u_1v_1$ and $D_2 - v_2u_2$ that assign the same color to $v_1$ and $v_2$ and taking the union of those colorings clearly leads to a $(k-1)$-coloring of $D$. Let $a \in A(D) \setminus \{u_1u_2\}$. By symmetry, we may assume that $a \in A(D_1)$. Then, there is a $(k-1)$-coloring $\varphi_1$ of $D_1 - a$ and a $(k-1)$-coloring $\varphi_2$ of $D_2 - v_2u_2$ such that $\varphi_1(v_1)=\varphi_2(v_2)$. By taking the union of those colorings we obtain a $(k-1)$-coloring of $D$ and so $D$ is $k$-critical, as claimed.

To prove statement (d) first assume that ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)=k$ but ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1)=k-1$. Then there is a $(k-1)$-coloring $\varphi$ of $D_1$. Since $D$ is $k$-critical, there furthermore exists a $(k-1)$-coloring $\varphi_2$ of $D_2 - v_2u_2$ with $\varphi_2(v_2)=\varphi_1(v_1)$ and the union of $\varphi_1$ and $\varphi_2$ is a $(k-1)$-coloring of $D$. Hence, ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1) \geq k$ and, by symmetry, we obtain ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2) \geq k$. In order to complete the proof we need to show that ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_i - a ) < k$ for $i \in \{1,2\}$ and for $a \in A(D_i)$. By symmetry, it suffices to show this for $D_1$. If $a = u_1v_1$, then ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1 - a) < k$ as $D_1 - a$ is a proper subdigraph of $D$ and therefore $(k-1)$-colorable. Let $a \in A(D_1) \setminus \{u_1v_1\}$. Then, there is a $(k-1)$-coloring $\varphi$ of $D - a$. We claim that the restriction of $\varphi$ to $V(D_1)$ is a $(k-1)$-coloring of $D_1 - a$. For otherwise, in $D_1 - a$ there would exist a monochromatic directed cycle $C_1$ that contains the arc $u_1v_1$. Since ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2) \geq k$, the restriction of $\varphi$ to $V(D_2)$ creates a monochromatic directed cycle $C_2$ in $D_2$ that contains the arc $u_2v_2$. However, $C_1 \cup C_2 - u_1v_1 - v_2u_2 + u_1v_1$ is a monochromatic directed cycle in $D - a$ with respect to $\varphi$, a contradiction. This completes the proof.

Another common operation for graphs and digraphs is the identification of independent sets. Let $D$ be a digraph and let $I$ be a non-empty independent set of $D$. Then, we can create a new digraph $H$ from $D-I$ by adding a new vertex $v=v_I$ and adding all arcs from $v$ to $N_H^+(I)= \bigcup_{v \in I} N_H^+(v)$ and all arcs from $N_H^-(I)=\bigcup_{v \in I}N_H^-(v)$ to $v$. We say that $H$ is obtained from $D$ by **identifying $I$ with $v$**, or briefly by **identifying independent vertices** and write $H=D/(I \to v)$ (briefly $H=D/I$). It is obvious that any $k$-coloring of $D/I$ can be extended to a $k$-coloring of $D$ by coloring each vertex of $I$ with the color of $v_I$. Thus, ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D/I) \geq {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)$.

We define the class of **Hajós-$k$-constructible digraphs** as the smallest family of digraphs that contains the bidirected complete graph of order $k$ and is closed ander Hajós joins and identifying independent vertices. The next result was proved for undirected graphs by Hajós [@Ha61].

\[theorem\_Hajos-constructible\] Let $k \geq 3$ be an integer. A digraph has chromatic number at least $k$ if and only if it contains a Hajós-$k$-constructible subdigraph.

For the proof of the above theorem we need a result on perfect digraphs. Recall that the **clique number** $\omega(D)$ of a digraph $D$ is the size of the largest bidirected complete subdigraph of $D$. A **perfect digraph** is a digraph $D$ satisfying that for each induced subdigraph $H$ of $D$ it holds ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(H)=\omega(H)$. Recall that an **odd hole** is an (undirected) cycle of odd length at least $5$ and an **odd antihole** is the complement of an odd hole. Moreover, a **filled odd hole/antihole** is a digraph $D$ so that $S(D)$ is an odd hole/antihole, where $S(D)$ is the **symmetric part** of $D$, that is, the graph with vertex set $V(D)$ and edge set $$E(S(D))=\{uv ~|~ uv \in A(D) \text{ and } vu \in A(D)\}.$$ Andres and Hochstättler [@AnHo15 Corollary 5] proved the following result on perfect digraphs.

\[theorem\_perfect-digraph\] A digraph $D$ is perfect if and only if it contains none of the following as an induced subdigraph: a filled odd hole, a filled odd antihole, or a directed cycle of length at least $3$ as induced subdigraph.

This theorem is a really nice and powerful tool in many ways. If $D=D(G)$ is a bidirected graph, then the theorem is equivalent to the Strong Perfect Graph Theorem (SPGT) by Chudnovsky, Robertson, Seymour, and Thomas [@CRST06], and hence, the SPGT follows from Andres and Hochstättler’s result. Nevertheless, their proof heavily relies on the SPGT.

Let $k\geq 3$ be an integer. Clearly, every Hajós-$k$-constructible digraph has chromatic number at least $k$ (by Theorem \[theorem\_Hajos-join\] and since ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D/I) \geq {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)$ for each independent set $I$ of a digraph $D$). This proves the “if”-implication. The proof of the “only if”-implication is by reductio ad absurdum. Let $D$ be a maximal counter-example in the sense that $D$ does not contain a Hajós-$k$-constructible subdigraph but adding a new arc $a \in A(\overline{D})$ to $D$ implies the existence of a Hajós-$k$-constructible subdigraph $D_a$ of $D + a$ with $a \in A(D_a)$. As $D$ is not Hajós-$k$-constructible, $D$ is not a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$. For two vertices $u,v \in V(D)$, let $u \sim v$ denote the relation that $uv \not \in A(D)$. We distinguish between two cases and show that both of them lead to a contradiction.

[[**Case 1:**]{} [*$\sim$ is transitive.*]{}]{} Then, in particular, the relation of being identical or non-adjacent in $D$ is an equivalence relation. This implies that $D$ is a semicomplete multipartite digraph with parts $I_1,I_2,\ldots,I_\ell$, *i.e.*, $I_j$ is an independent set in $D$ for $j \in \{1,2,\ldots,\ell\}$ and for $u \in I_i, v \in I_j$ with $i \neq j$, $A(D)$ contains at least one of $uv$ and $vu$. Suppose that there are vertices $u \in I_i, v \in I_j$ such that $u$ and $v$ induce a digon in $D$. Then we claim that each pair of vertices $(u',v') \in I_i \times I_j$ induces a digon in $D$. Otherwise, (by symmetry) there are vertices $u,u' \in I_i$ and a vertex $v \in I_j$ such that $\{uv, vu,u'v\} \subseteq A(D)$ but $vu' \not \in A(D)$. But then, $v \sim u', u' \sim u$ and $v \not \sim u$ and hence, $\sim$ is not transitive, a contradiction. This proves the claim that all arcs between $I_i$ and $I_j$ are bidirected. Moreover, by using a similar argumentation, it is easy to see that if there are vertices $u \in I_i, v \in I_j$ with $uv \in A(D)$ and $vu \not \in A(D)$, then $A_D(I_j,I_i)=\varnothing$. Now we claim that $D$ is perfect. By Theorem \[theorem\_perfect-digraph\] we only need to prove that $D$ does neither contain a filled odd hole, nor a filled odd antihole, nor an induced directed cycle of length at least $3$ as an induced subdigraph.

First assume that $D$ contains a filled odd hole $C$ as an induced subdigraph. Let $v_1,v_2,\ldots,v_r,v_1$ be a cyclic ordering of the vertices of the filled odd hole. By symmetry, we may assume that $v_3 \sim v_1$. As $\sim$ is transitive, this implies that $v_1v_4 \in A(D)$ (as otherwise $v_3 \sim v_1, v_1\sim v_4,$ but $v_3 \not \sim v_4$) and so $v_4 \sim v_1$. As a consequence, $v_1v_3 \in A(D)$ (since $v_4 \sim v_1$ and $v_4v_3 \in A(D)$). By continuing this argumentation we obtain that $v_1v_i \in A(D)$ for all $i \in \{2,\ldots,r\}$. Moreover, regarding $v_2$, it follows that $v_2v_4 \in A(D)$ (as otherwise $v_2 \sim v_4, v_4 \sim v_1,$ but $v_2 \not \sim v_1$, a contradiction). As a consequence, $v_2v_i \in A(D)$ for all $i \in \{4,5,\ldots,r\}$. Finally, $v_3v_r \in A(D)$ (as otherwise $v_3 \sim v_r, v_r \sim v_2$, but $v_3 \not \sim v_2$). However, since $C$ is a filled odd hole, this gives us $v_r \sim v_3$ and so $v_r \sim v_3, v_3 \sim v_1$, but $v_1 \not \sim v_r$, a contradiction. Thus, $D$ cannot contain a filled odd hole as an induced subdigraph.

Next assume that $D$ contains a filled odd antihole $C$ as an induced subdigraph. Let again $v_1,v_2,\ldots,v_r, v_1$ be a cyclic ordering of the vertices. By symmetry, we may assume that $v_1 \sim v_2$. Then, $v_2v_3 \in A(D)$ as otherwise $\sim$ would not be transitive. Continuing this argument, we obtain that $v_i\sim v_{i+1}$ for $i$ odd and $v_iv_{i+1} \in A(D)$ for even $i$. As $r$ is odd this implies $v_r \sim v_1$. As a consequence, $v_r \sim v_1, v_1 \sim v_2$, but $v_rv_2 \in A(D)$, a contradiction. Thus, $D$ contains no filled antiholes as induced subdigraphs.

Finally, assume that $D$ contains an directed cycle $C$ of length at least $3$ as an induced subdigraph. Again, let $v_1,v_2,\ldots,v_r, v_1$ be a cyclic ordering of the vertices of $C$. Then, $v_1 \sim v_r, v_r \sim v_2$, but $v_1v_2 \in A(D)$, a contradiction. As a consequence, $D$ is perfect by Theorem \[theorem\_perfect-digraph\] and so $D$ contains a bidirected complete graph of order at least $k$ as a subdigraph and, therefore, a Hajós-$k$-constructible sudigraph, which is impossible.

[[**Case 2:**]{} [*$\sim$ is not transitive.*]{}]{} Then there are vertices $u,v,w \in V(D)$ such that $uv \not \in A(D)$, $vw \not \in A(D)$, but $uw \in A(D)$. By the maximality of $D$, there exist Hajós-$k$-constructible subdigraphs $D_{uv} \subseteq D + uv$ and $D_{vw} \subseteq D + vw$. Let $D'$ be the graph obtained from the union $(D_{uv} - uv) \cup (D_{vw} - vw)$ by adding the arc $uw$. Then, $D'$ is a subdigraph of $D$ that can be obtained from disjoint copies of $D_{uv}$ and $D_{uw}$ as follows. First we apply the Hajós join by removing the copies of the arcs $uv$ and $vw$, identifying the two copies of $v$, and adding the arc $uw$. Afterwards, for each vertex $x$ that belongs to both $D_{uv}$ and $D_{vw}$, we identify the two copies of $x$. Hence, $D'$ is a Hajós-$k$-constructible subdigraph of $D$, a contradiction. This completes the proof.

In the last two decades Hajós’ theorem (Theorem \[theorem\_Hajos-constructible\]) became very popular among graph theorists. Hajós like theorems were established for the list chromatic number by Gravier [@Gravier96] and Král [@Kral2004], for the circular chromatic number by Zhu [@Zhu2003], for the signed chromatic number by Kang [@Kang2018a], for the chromatic number of edge weighted graphs by Mohar [@Mohar2004], for graph homomorphisms by Nešetril [@Nesetril99], and for Grassmann homomorphism (a homomorphism concept that provides a common generalization of graph colorings, hypergraph colorings and nowhere-zero flows) by Jensen [@Jensen2017].

The Ore construction
====================

Regarding undirected graphs, Urquhart [@Ur97] proved that each graph with chromatic number at least $k$ does not only contain a Hajós-$k$-constructible subgraph but itself is Hajós-$k$-constructible. Recall that a **Hajós join** of two undirected disjoint graphs $G_1$ and $G_2$ is done by deleting two edges $e=uv \in E(G_1)$ and $e'=u'v' \in E(G_2)$, identifying the vertices $v$ and $v'$, and adding the edge $uu'$. The aim of this section is to point out that the same result does not hold for digraphs and to prove that, however, a slight modification of the Hajós join does the trick. The proof of the next theorem is straightforward and left to the reader.

Let $k \geq 3$ be an integer and let $D$ be a Hajós-$k$-constructible digraph. Then, $D$ is strongly connected.

As a consequence of the above theorem, every digraph with chromatic number at least $k$ that is not strongly connected is not Hajós-$k$-constructible and so Urquhart’s Theorem cannot be directly transferred to digraphs. Nevertheless, it turns out that we get an Urquhart-type theorem by further allowing the following join. Let $D_1$ and $D_2$ be two digraphs and let $u_1,v_1 \in V(D_1)$ and $u_2,v_2 \in V(D_2)$ such that $D_i[\{u_i,v_i\}]$ is a digon for $i \in \{1,2\}$. Now let $D$ be the digraph obtained from the union $D_1 \cup D_2$ by deleting both arcs between $u_1$ and $v_1$ as well as both arcs between $u_2$ and $v_2$, identifying the vertices $v_1$ and $v_2$ to a new vertex $v$, and adding both arcs $u_1u_2$ and $u_2u_1$. We say that $D$ is the **bidirected Hajós join** of $D_1$ and $D_2$ and write $D= (D_1,v_1,u_1) {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}} (D_2,v_2,u_2)$ or, briefly, $D=D_1 {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}} D_2$. Note that the bidirected Hajós join is the exact analogue of the undirected Hajos join. By a slight modification of the proof of Theorem \[theorem\_Hajos-join\](a)-(c) one can easily show that the following holds.

\[theorem\_bidirected-Hajos-join\] Let $D=D_1 {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}} D_2$ result from the bidirected Hajós join of two disjoint non-empty digraphs $D_1$ and $D_2$. Then, the following statements hold:

-   ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) \geq \min\{{\overset{\text{\tiny$\bm\rightarrow$}}{\chi}} (D_1), {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2)\}$.

-   If ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_1)={\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D_2)=k$ and $k \geq 3$, then ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)=k$.

-   If both $D_1$ and $D_2$ are $k$-critical and $k \geq 3$, then $D$ is $k$-critical.

Note that for the proof of statement (b), we use the fact that $k \geq 3$ and so we can choose $\varphi_1$ and $\varphi_2$ such that $\varphi_1(v_1)=\varphi_2(v_2)$ and $\varphi_1(u_1) \neq \varphi_2(u_2)$. For $k=2$, the statement is not true: for example, ${\overset{\text{\tiny$\bm\leftrightarrow$}}{C_4}} {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}} {\overset{\text{\tiny$\bm\leftrightarrow$}}{C_4}}= {\overset{\text{\tiny$\bm\leftrightarrow$}}{C_7}}$, whereas ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}({\overset{\text{\tiny$\bm\leftrightarrow$}}{C_4}})=2 \neq 3 = {\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}({\overset{\text{\tiny$\bm\leftrightarrow$}}{C_7}})$. The same trick works for statement (c).

For the proof of his Theorem, Urquhart even used a more restricted class of constructible (undirected) graphs than the class of Hajós-$k$-constructible graphs, which originally was introduced by Ore [@Ore67 Chapter 11]. Transferred to digraphs, we get the following. Let $D_1$ and $D_2$ be two vertex-disjoint digraphs, let $u_1v_1$ be an arc of $D_1$, and let $v_2u_2$ be an arc of $D_2$. Furthermore, let $\iota: A_1 \to A_2$ be a bijection with $A_i \subseteq V(G_i - v_i)$ for $i \in \{1,2\}$ and $\iota(u_1) \neq u_2$. Let $D$ be the digraph obtained from $(D_1,v_1,u_1)\triangledown (D_2,v_2,u_2)$ by identifying $w$ with $\iota(w)$ for each $w \in A_1$. Then, $D$ is a **directed Ore join** of $D_1$ and $D_2$ and we write $D=(D_1,v_1,u_1)\triangledown^o_\iota (D_2,v_2,u_2)$. Similar, if $u_1,v_1 \in V(D_1)$ and $u_2,v_2 \in V(D_2)$ are vertices such that $D_i[\{u_i,v_i\}]$ is a digon for $i \in \{1,2\}$ and if $\iota$ is the bijection from above, then the digraph $D$ obtained from $ (D_1,v_1,u_1) {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}} (D_2,v_2,u_2)$ by identifying $w$ with $\iota(w)$ for each $w \in A_1$ is a **bidirected Ore join** of $D_1$ and $D_2$ and we write $D=(D_1,v_1,u_1){\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}}^o_\iota (D_2,v_2,u_2)$.

We define the class of **Ore-$k$-constructible** digraphs as the smallest family of digraphs that contains ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ and is closed under (directed and bidirected) Ore joins. The proof of Theorem \[theorem\_Hajos-constructible\] immediately implies the following theorem (see [@Ore67] for the undirected analogue). In particular, here we do not need any bidirected Ore joins.

Let $k \geq 3$ be an integer. A digraph has chromatic number at least $k$ if and only if it contains an Ore-$k$-constructible subdigraph.

Urquhart proved the following, thereby answering a conjecture by Hanson, Robinson and Toft [@HaRoTo86] (the conjecture was also proposed by Jensen and Toft in their book on graph coloring problems [@JeTo95]). Recall that the Ore join of two undirected graphs is done via an undirected Hajós join and identification afterwards.

Let $k \geq 3$ be an integer. For a graph $G$ the following conditions are equivalent:

-   $G$ is Ore-$k$-constructible.

-   $G$ is Hajós-$k$-constructible.

-   The chromatic number of $G$ satisfies $ \chi(G) \geq k$.

Note that if $G$ is the Hajós join of two graphs $G_1$ and $G_2$, then $D(G)$ is the bidirected Hajós join of $D(G_1)$ and $D(G_2)$. Furthermore, ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D(G)) = \chi(G)$ and so the above theorem immediately implies the following.

Each bidirected graph with chromatic number at least $k \geq 3$ is Ore-$k$-constructible. \[observation\_bidirected\]

Now we have all the tools that we need in order to prove our Urquhart-type theorem.

\[theorem\_Ore-join\] Let $k \geq 3$ be an integer. A digraph has chromatic number at least $k$ if and only if it is Ore-$k$-constructible.

It immediately follows from Theorem \[theorem\_Hajos-join\](a) and Theorem \[theorem\_bidirected-Hajos-join\](a) that each Ore-$k$-constructible digraph has chromatic number at least $k$.

Thus, it suffices to show that each digraph with chromatic number $\geq k$ is Ore-$k$-constructible. We will do this via a sequence of claims. In the following, we will denote by ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + {\overset{\text{\tiny$\bm\rightarrow$}}{v}}$ (respectively ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} +  {\overset{\text{\tiny$\bm\leftarrow$}}{v}}$) the digraph that results from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ by adding a vertex $v$ and the arc $uv$ (respectively $vu$) for some vertex $u$ of the ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$. Moreover, let ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + a$ be the digraph that results from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ by adding two new vertices $u,v$ and the arc $a=uv$. Finally, $\mathcal{O}_k$ denotes the class of Ore-$k$-constructible digraphs and $\mathcal{O}_k^*$ denotes the class of Ore-$k$-constructible digraphs containing a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$. It follows from Observation \[observation\_bidirected\] that

The digraph obtained from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ by adding an isolated vertex belongs to $\mathcal{O}_k^*$.

\[claim\_K+a\] The digraph ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + a$ belongs to $\mathcal{O}_k^*$.

It is clear that ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + a$ still contains the ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$. We claim that ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + a$ is Ore-constructible. To this end, let $D_1$ (respectively $D_2$) be the bidirected graph obtained by identifying a vertex of ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ to a vertex of a disjoint ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_2}}$ (respectively ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_3}}$). More formally, $V(D_1)=\{v_1,v_2,\dots,v_k,u\}$, $V(D_2)=\{v'_1,v_2',\dots,v'_k,u_1,u_2\}$, $A(D_1)=\{v_iv_j ~|~ i\neq j\}\cup\{v_1u,uv_1\}$ and $A(D_2)=\{v'_iv'_j ~|~ i\neq j\}\cup\{v'_1u_1,v'_1u_2,u_1v'_1,u_2v'_1,$ $u_1u_2,u_2u_1\}$ (see Figure \[figG1G2\]). Let $\iota$ be the bijection with $\iota(v_i)=v'_i$ for all $i \in \{1,2,\ldots,k\}$ and let $D'_2=(D_1,u,v_1) \triangledown^o_\iota (D_2,u_2,u_1)$ (see Figure \[figure\_K\_k+a\](a) and (b)). This Ore-join leads to the digraph $D'_2=D_2-u_2u_1$ (see Figure \[figure\_K\_k+a\](c)). By $v_i^*$ we denote the vertex that results from identifying $v_i$ with $\iota(v_i)=v_i'$.

![The digraphs $D_2$ (on the left) and $D_1$ (on the right).[]{data-label="figG1G2"}](figure_first-step_a.png){width=".5\textwidth"}

\

![This leads to the graph $D'_2$.[]{data-label="figG’2"}](figure_first-step_b.png){width=".5\textwidth"}

\

![This leads to the graph $D'_2$.[]{data-label="figG’2"}](figure_first-step_c.png){width=".3\linewidth"}

Now we take a new copy of $D_1$, define $\iota'$ to be the bijection with $\iota'(v^*_i)=v_{i+1}$ for all $i \in \{1,2,\ldots,k\}$ (where $v_{k+1}=v_1$), and set $D''=(D',u_1,v^*) {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}}^o_{\iota'} (D_1,u,v_1)$ (see Figure \[figure\_K\_k+a\](d)(e)). Still, let $v_i^*$ denote the vertex that results from identifying $v^*_i$ with $\iota'(v^*_i)$.

[0.58]{} ![The graph $D''_2$.[]{data-label="figG”2"}](figure_second-step_a.png "fig:"){width=".7\linewidth"}

[0.38]{} ![The graph $D''_2$.[]{data-label="figG”2"}](figure_second-step_b.png "fig:"){width=".6\linewidth"}

\

Finally, we take another copy of $G_1$, set $\iota''(v^*_i)=v_{i+1}$ for $i \in \{1,2,\ldots,k\}$ (where $v_{k+1}=v_1$) and perform the Ore join $(D_2'',u_2,v^*){\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}}^o_{\iota''}(G_1,v_1,u)$ (see Figure \[figure\_K\_k+a\](f)(g)). This gives us the digraph $K_k + u_1u_2$ as required.

[0.58]{} ![The construction of Claim 2.[]{data-label="figure_K_k+a"}](figure_final-step_a.png "fig:"){width=".7\linewidth"}

[0.38]{} ![The construction of Claim 2.[]{data-label="figure_K_k+a"}](figure_final-step_b.png "fig:"){width=".6\linewidth"}

By using a similar construction starting with the graph that results from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ by adding a vertex $v$ and joining it to two vertices of ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ by arcs in both directions we obtain the following. For the exact construction see Figure \[fig\_claim\_K+v\].

\[claim\_K+v\] The digraphs ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + {\overset{\text{\tiny$\bm\rightarrow$}}{v}}$ and ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + {\overset{\text{\tiny$\bm\leftarrow$}}{v}}$ are in $\mathcal{O}_k^*$.

![End of the first step.](figure_K+v_a.png){width=".4\linewidth"}

[0.58]{} ![End of the first step.](figure_K+v_b.png "fig:"){width=".6\linewidth"}

[0.38]{} ![End of the first step.](figure_K+v_c.png "fig:"){width=".5\linewidth"}

![The construction of Claim \[claim\_K+v\].[]{data-label="fig_claim_K+v"}](figure_K+v_d.png){width=".4\linewidth"}

[0.58]{} ![The construction of Claim \[claim\_K+v\].[]{data-label="fig_claim_K+v"}](figure_K+v_e.png "fig:"){width=".6\linewidth"}

[0.38]{} ![The construction of Claim \[claim\_K+v\].[]{data-label="fig_claim_K+v"}](figure_K+v_f.png "fig:"){width=".5\linewidth"}

From now on, we may argue similar to the original proof of Urquhart. The next claim can easily be deduced from Claim 1.

Let $D$ be a digraph belonging to $\mathcal{O}_k^*$. Then, the digraph $D'$ obtained from $D$ by adding an isolated vertex belongs to $\mathcal{O}_k^*$, too. \[claim\_isolated-vertex\]

Let $D$ be a digraph belonging to $\mathcal{O}_k^*$ and let $a \in A(\overline{D})$. Then, the digraph $D + a$ belongs to $\mathcal{O}_k^*$, too. \[claim\_new-edge\]

Since $D \in \mathcal{O}_k^*$, there is a vertex set $X \subseteq V(D)$ such that $D[X]$ is a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K}}_k$. We distuingish between two cases.

[[**Case 1:**]{} [*One end-vertex of the arc $a$ belongs to $X$.*]{}]{} Then, let $a=uv$ with $u \in X$ and $v \in V \setminus X$ (the case $a=vu$ can be done analogously). Furthermore, let $D'$ be a copy of ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + {\overset{\text{\tiny$\bm\rightarrow$}}{v'}}$ and let $u'$ be the vertex adjacent to $v'$ in $D'$. Finally, let $w, z \in X \setminus\{u\}$ and let $w', z' \in D' \setminus \{u',v'\}$. By Claim \[claim\_K+v\], $D' \in \mathcal{O}_k$. Now let $\iota$ be a bijection from $(X\setminus \{u\}) \cup \{v\}$ to $(X'\setminus \{u'\}) \cup \{v'\}$ with $\iota(v) = v'$, $\iota(w)=z'$, and $\iota(z)=w'$. Then, $(D,u,w) {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown^o_\iota}} (D',u',w') \in \mathcal{O}_k$ is a copy of $D+a$, and we are done.\
[[**Case 2:**]{} [*No end-vertex of $a$ belongs to $X$.*]{}]{} Then, let $a=uv$, and $D'$ be a copy of ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}} + u'v'$. By Claim \[claim\_K+a\], $D'$ belongs to $\mathcal{O}_k$. Now let $x,y,z$ be three vertices from $X$ and let $\{x',y',z'\} \subseteq D' \setminus \{u,v\}$. Finally, let $\iota$ be a bijection from $X \setminus \{x\} \cup \{u,v\}$ to $D' \setminus \{x'\}$ with $\iota(u)=u'$, $\iota(v)=v'$, $\iota(y)=z'$, and $\iota(z)=y'$. Then, $(D,x,y) {\overset{\text{\tiny$\bm\leftrightarrow$}}{\triangledown}}^o_\iota (D',x',y')\in \mathcal{O}_k$ is a copy of $D + a$ and the proof of the claim is complete.

It follows from Claims \[claim\_isolated-vertex\] and \[claim\_new-edge\] that each digraph containing a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ belongs to $\mathcal{O}_k^*$. The remaining part of the proof is by reductio ad absurdum. Let $D$ be a maximal counterexample in the sense that ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D) \geq k$, $D$ is not Ore-$k$-constructible, and $D$ has maximum number of edges with respect to this property. Then, $D$ does not contain a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ and if $a \in A(\overline{D})$, $D+a$ belongs to $\mathcal{O}_k$. Now we argue as in the proof of Theorem \[theorem\_Hajos-constructible\]. For two vertices $u,v \in V(D)$, let $u \sim  v$ denote the relation that $uv \not \in A(D)$. If $\sim$ is transitive we again conclude that $D$ contains a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$, a contradiction. Hence, $\sim$ is not transitive and so there are vertices $u,v,w \in V(D)$ with $uv \not \in A(D)$, $vw \not \in A(D)$, but $uw \in A(D)$. Then, both digraphs $D+uv$ as well as $D+vw$ belong to $\mathcal{O}_k$ and $D$ is the Ore join of two disjoint copies of these two digraphs. Thus, $D$ belongs to $\mathcal{O}_k$, a contradiction.

A Gallai-type theorem for critical digraphs {#section_gallai}
===========================================

Let $D$ be a $k$-critical digraph. If $v \in V(D)$, then $D-v$ admits a $(k-1)$-coloring and, since ${\overset{\text{\tiny$\bm\rightarrow$}}{\chi}}(D)=k$, $v$ must have an out- and an in-neighbor in each color class of such a coloring. Hence, we have $k-1 \leq \min \{d_D^+(v),d_D^-(v)\}$ for every vertex $v \in V(D)$, which gives us a natural way to classify the vertices of $D$. We say that a vertex $v \in V(D)$ is a **low-vertex** of $D$ if $d_D^+(v)=d_D^-(v)=k-1$ and a **high vertex**of $D$, otherwise. Furthermore, let $D_L$ denote the digraph that is induced by the set of low vertices of $D$; we will call it the **low vertex subdigraph** of $D$. For undirected graphs, Gallai [@Gal63a] proved that the low vertex subgraph has a specific structure. The next theorem transfers his result to digraphs.

\[theorem\_gallai\] Let $D_L$ be the low vertex subdigraph of a $k$-critical digraph $D$. Then, each block $B$ of $D_L$ satisfies one of the following statements.

-   $B$ consists of just one single arc.

-   $B$ is a directed cycle of length $\geq 2$.

-   $B$ is a bidirected cycle of odd length.

-   $B$ is a complete bidirected graph.

For the proof of Theorem \[theorem\_gallai\] we will use a theorem of Harutyunyan and Mohar [@HaMo11] concerning list-colorings of digraphs. Given a digraph $D$, a **list-assignment** $L$ is a function that assigns each vertex $v \in V(D)$ a set (list) of colors. An $L$**-coloring** $\varphi$ of $D$ is a coloring of $D$ such that $\varphi(v) \in L(v)$ for all $v \in V(D)$.

\[theorem\_harut\] Let $D$ be a connected digraph, and let $L$ be a list-assignment such that $|L(v)| \geq \max \{d_D^+(v), d_D^-(v)\}$ for all $v \in V(D)$. Suppose that $D$ is not $L$-colorable. Then, $D$ is Eulerian and for every block $B$ of $D$ one of the following cases occurs:

-   $B$ is a directed cycle of length $\geq 2$.

-   $B$ is a bidirected cycle of odd length $\geq 3$.

-   $B$ is a bidirected complete graph.

The next proposition states some important facts that will be needed for the proof of Theorem \[theorem\_gallai\].

\[prop\_shifting\] Let $D_L$ be the low vertex subdigraph of a $k$-critical digraph $D$. Moreover, given a vertex $v \in V(D_L)$, let $\varphi$ be a $(k-1)$-coloring of $D - v$ with color set $C$. Then the following statements hold:

-   Each color from $C$ appears exactly once in $N^+(v)$ and in $N^-(v)$.

-   If $u \in V(D_L)$ is adjacent to $v$, then uncoloring $u$ and coloring $v$ with the color of $u$ leads to a $(k-1)$-coloring of $D-u$.

Suppose (by symmetry) that there is a color $\alpha \in C$ such that $\alpha$ does not appear in $N^+(v)$. Then, coloring $v$ with $\alpha$ cannot create a monochromatic cycle in $D$ (as $v$ has no out-neighbor with color $\alpha$) and, thus, $D$ would be $(k-1)$-colorable, a contradiction. As $d_D^+(v)=k-1=|C|$, this proves (a).

For the proof of (b), assume (by symmetry) that $uv \in A(D)$. Then it follows from (a) that after uncoloring $u$, $v$ has no in-neighbor with color $\varphi(u)$ and so coloring $v$ with color $\varphi(u)$ cannot create a monochromatic cycle.

In the following, we will call the procedure that is described in Proposition \[prop\_shifting\] (b) **shifting** the color from $u$ to $v$ and briefly write $u \to v$. Now let $D$ be a $k$-critical digraph, let $C$ be a (not necessarily directed) cycle in $D_L$ and let $v \in V(C)$. Moreover, let $\varphi$ be a $(k-1)$ coloring of $D - v$ and let $u$ and $w$ be the vertices such that $u,v$ and $w$ are consecutive in $C$. Then, beginning with $u \to v$, we can shift each vertex of $C$, one after another, clockwise and obtain a new $(k-1)$-coloring of $D - v$ (see Figure \[fig\_shift-example\]). Similar, beginning with $w \to v$, we can shift each vertex of $C$ counter-clockwise and obtain a third $(k-1)$-coloring of $D-v$. The main idea for this goes back to Gallai [@Gal63a]; we will use this observation frequently in the following.

Let $D_L$ be the low vertex subdigraph of a $k$-critical digraph $D$ and let $B$ be an arbitrary block of $D_L$. If $|B|=1$, then $B={\overset{\text{\tiny$\bm\leftrightarrow$}}{K_1}}$ and we are done. If $|B|=2$, then either $B$ consists of just one arc or $B$ is a bidirected complete graph and so there is nothing to show. Thus, we may assume $|B| \geq 3$.

\[claim\_eulerian\] For all vertices $v \in V(B)$ we have $d_{B}^+(v) = d_{B}^-(v)$ and so $B$ is Eulerian.

For otherwise, we may assume that $d_B^+(v) < d_B^-(v)$ for some $v \in V(B)$. Let $\varphi$ be a $(k-1)$-coloring of $D-v$. Since $d_D^+(v)=d_D^-(v) = k-1$, it follows from Proposition \[prop\_shifting\](a) that there is a color $\alpha$ that appears in $N_B^-(v)$ but not in $N_B^+(v)$. Let $u$ be the vertex from $N_B^-(v)$ with $\varphi(u)=\alpha$. Note that Proposition \[prop\_shifting\](a) furthermore implies that there is a vertex in $v' \in N_D^+(v) \cap (V(D) \setminus V(B))$ that has color $\alpha$. First we show that $d_B^+(v)=0$. Suppose, to the contrary, that $d^+_B(v) > 0$ and let $w$ be an out-neighbor of $v$ in $D_L$. Then, in $B$ there is a (not-necessarily directed) induced cycle $C$ such that $u,v$ and $w$ are consecutive on $C$. Beginning with $u \to v$, we shift all vertices of $C$ clockwise and obtain a new $(k-1)$-coloring $\varphi'$ of $D-v$ with $\varphi'(w)=\alpha$. Since no vertex from $V(D) \setminus V(C)$ took part in the shifting, we have $\varphi'(v')=\varphi(v')=\alpha$ and so $\alpha$ appears twice in $N_D^+(v)$, contradicting Proposition \[prop\_shifting\](a). This proves that $d_B^+(v)=0$.

Let again $C$ be an (undirected) induced cycle in $B$ such that $u$ and $v$ are consecutive on $C$ and let $w$ be the other neighbor of $v$ in $C$. Then, $w$ is also an in-neighbor of $v$ (as $d_B^+(v)=0$). Thus, it follows from Proposition \[prop\_shifting\](a) that $\varphi(w)\neq \varphi(u)$, say $\varphi(w)=\beta$. Moreover, we obtain that the vertices of $C$ (except from $v$) are colored alternately with $\beta$ and $\alpha$. Otherwise, there are two consecutive vertices $x,x'$ on $C$ such that $\{\varphi(x), \varphi(x')\} \neq \{\alpha, \beta\}$. Then we can shift the colors around the vertices of $C$ such that $u$ gets color $\varphi(x)$ and $w$ gets color $\varphi(x')$ and obtain a $(k-1)$-coloring $\varphi'$ of $D-v$ with $\{\varphi'(u), \varphi'(w)\} \neq \{\alpha,\beta\}$, which contradicts Proposition \[prop\_shifting\](a) as $C$ is induced and so no neighbors of $v$ besides $u$ and $w$ take part in the shifting.

As a consequence, $C$ has odd length. Now let $v=v_1,w=v_2,v_3,\ldots,u=v_r,v_1$ be a cyclic ordering of the vertices of $C$. We claim that $v_3v_2 \not \in A(D)$. Assume, to the contrary, $v_3v_2 \in A(D)$. Then, we can shift $w \to v$ and obtain a coloring $\varphi'$ of $D-w$ with $\varphi'(v)=\beta$ and $\varphi'(v_3)= \alpha$. In particular, $v_3$ is the only in-neighbor of $w$ that has color $\alpha$ with respect to $\varphi'$. On the other hand, beginning from $\varphi$ with $u \to v$, we can shift every vertex besides $v$ clockwise around $C$ (the last shift is $w \to v_3$) and get a $(k-1)$-coloring $\varphi^*$ of $G-w$ with $\varphi^*(v) = \alpha$ and $\varphi^*(v_3)= \beta$. As $vw \not \in A(D)$ and as $C$ is induced, it follows that $w$ has no in-neighbor that has color $\alpha$ with respect to $\varphi^*$, a contradiction. Hence, $v_3v_2 \in A(D)$ and so $v_2v_3 \in A(D)$. By repeating this argumentation, we obtain that $v_{i+1}v_i \not \in A(D)$ but $v_iv_{i+1} \in A(D)$ for $i \geq 2$ even and that $v_iv_{i+1} \not \in A(D)$ but $v_{i+1}v_i \in A(D)$ for $i \geq 3$ odd. In particular, this leads to $v_rv \not \in  A(D)$, a contradiction. This proves the claim.

Now let $\varphi$ be a $(k-1)$-coloring of $D-B$ with color set $C$. For $v \in V(B)$, let $$L(v) = C   \setminus \varphi(N_D^+(v) \setminus V(B)).$$ then, as $d_D^+(v)=d_D^-(v)=k-1=|C|$ and since $d_B^+(v)=d_B^-(v)$ by Claim \[claim\_eulerian\], we have $|L(v)| \geq \max \{d_B^+(v), d_B^-(v)\}$ for all $v \in V(B)$. Moreover, $B$ is not $L$-colorable, as the union of any $L$-coloring of $B$ with $\varphi$ would clearly lead to a $(k-1)$-coloring of $D$. Hence, we can apply Theorem \[theorem\_harut\] and so $B$ is a directed cycle, or an odd bidirected cycle, or a bidrected complete graph, as claimed.

In the undirected case, Gallai [@Gal63a] showed that the only blocks of the low vertex graph are complete graphs or odd cycles. Although for digraphs the directed cycles arise naturally, it may surprise that there can also be blocks that consist of just one arc. That this indeed may happen is illustrated in Figure \[fig\_K\_4Haj\], where we show the Hajós join of two ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_4}}$; here the low vertex subdigraph consists of every vertex except the identified vertex $v$. Clearly, by starting from a ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$ and iteratively taking Hajós joins with another ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$, we can even create infinite families of digraphs $D$ such that there are blocks of $D_L$ consisting of just a single arc.

Gallai used the characterization of the low vertex subgraph of critical graphs he obtained in [@Gal63a] to establish a lower bound for the number of edges of critical graphs. We can apply the same approach to obtain a similar bound for the number of arcs in critical digraphs, see also [@SchwST2017].

\[corollary:gallaibound\] Let $D$ be a $(k+1)$-critical digraph with $k\geq 3$ and without digons. Then $$2|A(D)|\geq \left( 2k+\frac{2k-2}{(2k+1)^2-3} \right)|D|$$ unless $D={\overset{\text{\tiny$\bm\leftrightarrow$}}{K}}_{k+1}$.

Let $V=V(D)$ and let $n=|V|$. For a set $X\subseteq V$, let $a(X)$ denote the number of arcs of $D[X]$. Furthermore, let $$R=\left(2k+\frac{2k-2}{(2k+1)^2-3} \right).$$ Our aim is to show that $2a(V)\geq Rn$. Let $U=V(D_L)$ be the set of low vertices of $D$ and let $W=V{\setminus}U$. If $U={\varnothing}$, then $2a(V)\geq (2k+1)n\geq Rn$ and we are done. So assume that $U\not={\varnothing}$. Since $D$ has no digons and $D\not={\overset{\text{\tiny$\bm\leftrightarrow$}}{K}}_{k+1}$, it follows that ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K}}_{k+1}$ is no subdigraph of $D$. By Theorem \[theorem\_gallai\], each block of $D_L$ consists of exactly one arc or is a directed cycle of length $\geq 3$. Then, see [@SchwST2017 Lemma 3.3], we have $$\left( 2k-1+\frac{1}{k}\right)|U|-2a(U)\geq 2.$$ Since every vertex of $U$ has total degree $2k$ in $D$ (i.e., $d_D^+(v)+d_D^-(v)= 2k$ for all $v\in U$) and $n=|U|+|W|$, we then obtain that $$2a(V)=2a(W)+4k|U|-2a(U)\geq 4k|U|-2a(U)\geq \left(2k+1-\frac{1}{k}\right)|U|+2$$ On the other hand, since every vertex in $W$ has total degree at least $2k+1$, we obtain that $$2a(V)\geq 2kn+|W|\geq (2k+1)n-|U|.$$ Adding the first inequality to the second inequality multiplied with $(2k+1-1/k)$ yields $$2a(V)(2k+2-1/k)\geq (2k+1-1/k)(2k+1)n+2.$$ As $(2k+2-1/k)=((2k)^2+4k-2)/(2k)>0$, this leads to $$2a(V)\geq \frac{((2k)^2+2k-2)(2k+1)n+4k}{(2k)^2+4k-2}\geq Rn.$$ Thus the proof is complete.

Open Questions
==============

Since the field of critical digraphs is still wide open, a lot of questions immediately come to mind. It follows from Theorem \[theorem\_Hajos-constructible\] that each $k$-critical digraph is Hajós-$k$-constructible. However, the proof of Theorem \[theorem\_Hajos-constructible\] is not constructive at all and the authors feel quite embarrassed in admitting that they could not even manage to construct a bidirected cycle of length five from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_4}}$’s using Hajós joins and identification of non-adjacent vertices. Thus, we want to pose the following question.

How can a bidirected $C_5$ be constructed from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_4}}$’s by only using Hajós joins and identifying non-adjacent vertices?

Building upon this question, it is of particular interest to study the connection of the Hajós construction to computational complexity. In the undirected case, Mansfield and Welsh [@MaWe82] stated the problem of determining the complexity of the Hajós construction. They noted that if for any $k \geq 3$ there would exist a polynomial $P$ such that every graph of order $n$ with chromatic number $k$ contains a Hajós-$k$-constructible subgraph that can be obtained by at most $P(n)$ uses of the Hajós-join and identification of non-adjacent vertices, then $\NP = \coNP$. Hence, it is very likely that the Hajós construction is not polynomially bounded but not much progress has been made on this problem yet. Pitassi and Urquhart [@PiUr95] found a linkage to another important open problem in logic; they proved that a restricted version of the Hajós construction is polynomially bounded if and only if extended Frege systems are polynomially bounded.

For $k \geq 3$, is there a polynomial $P$ such that every digraph of order $n$ contains a Hajós-$k$-constructible subdigraph that can be obtained from ${\overset{\text{\tiny$\bm\leftrightarrow$}}{K_k}}$’s by at most $P(n)$ uses of the Hajós-join and identification of non-adjacent vertices?

A beautiful theorem of Gallai [@Gal63b] states that any $k$-critical graph with order at most $2k-2$ and $k \geq 2$ is the Dirac join of two disjoint non-empty critical graphs (for the Dirac join of two undirected graphs just add all possible edges between the two graphs $G_1$ and $G_2$). Within the last decades, various different proofs of this theorem have been published (see e.g. [@Mol99] and [@Ste03]). Clearly, a graph $G$ is the Dirac join of two disjoint non-empty graphs if and only if $\overline{G}$ is disconnected and so most of the proofs use matching theory for the complement graph $\overline{G}$. However, it is yet unclear how to do this for digraphs.

Let $k \geq 3$ be an integer. Is there a $k$-critical digraph $D$ on at most $2k - 2$ vertices that is not the Dirac join of two proper digraphs $D_1$ and $D_2$?

In coloring theory of digraphs, it is often of particular interest how digon-free digraphs behave. For example, it was shown by Harutyunyan in his PhD thesis [@Ha11] that almost all tournaments of order $n$ have chromatic number at least $\frac{1}{2}(\frac{n}{\log n + 1})$. As a consequence, if $n$ is large enough then for some $k \geq \frac{1}{2}(\frac{n}{\log n + 1})$ there are $k$-critical digon-free digraphs on at most $n$ vertices. This leads to our final question.

For fixed $k \geq 3$, what is the minimum integer $N(k)$ such that there is a $k$-critical digon-free digraph on $N(k)$ vertices?

As $k-1 \leq \min \{ d_D^+(v), d_D^-(v)\}$ for all vertices $v$ of a $k$-critical digraph $D$, we trivially have $N(k) \geq 2k-1$. In fact, Brooks’ theorem for digraphs [@Mo10] implies that $N(k) \geq 2k$ for $k\geq 3$. Moreover, some small values are already known: the directed triangle shows that $N(2) = 3$, and Neumann-Lara [@NeuLa94] proved that $N(3) = 7$, $N(4) = 11$, and $17 \leq N(5) \leq 19$; he conjectured that $N(5) = 17$.

[99]{} S. D. Andres and W. Hochstättler. Perfect digraphs. [[*J Graph Theory*]{} [**79**]{} (2015) 21–29.]{}

J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer Science & Business Media 2008.

J. Bensmail, A. Harutyunyan, and N. Khang Le. List coloring digraphs. [[*J Graph Theory*]{} [**87**]{} (2018) 492–508.]{}

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. [[*Ann. Math.*]{} [**164**]{} (2006) 51–229.]{}

T. Gallai. Kritische Graphen I. [[*Publ. Math. Inst. Hungar. Acad. Sci.*]{} [**8**]{} (1963) 165–192.]{}

T. Gallai. Kritische Graphen II. [[*Publ. Math. Inst. Hungar. Acad. Sci.*]{} [**8**]{} (1963) 373–395.]{} S. Gravier. A Hajós-like theorem for list coloring. [[**]{} [**152**]{} (1996) 299–302.]{} G. Hajós. Über eine Konstruktion nicht $n$-färbbarer Graphen. [[*Wiss. Z.Martin Luther Univ. Halle-Wittenberg, Math.-Natur. Reihe*]{} [**10**]{} (1961) 116–117.]{}

D. Hanson, G. C. Robinson, and B. Toft. Remarks on the graph colour theorem of Hajós. [[*Cong. Numer.*]{} [**55**]{} (1986) 69–76.]{}

A. Harutyunyan, Brooks type results for coloring of digraphs, Simon Fraser University Vancouver 2011.

A. Harutyunyan and B. Mohar. Strengthened Brooks Theorem for digraphs of girth three. [[*Electr. J. Combin.*]{} [**18.1**]{} (2011) \#195.]{}

A. Harutyunyan and B. Mohar. Gallai’s theorem for list coloring of digraphs. [[*SIAM J Discrete Math.*]{} [**25**]{} (2011) 170–180.]{}

R. Hoshino and K. Kawarabayashi. The edge density of critical digraphs. [[*Combinatorica*]{} [**35**]{} (2015) 619–631.]{}

T. R. Jensen. Grassmann homomorphism and Hajós type theorems. [[*Linear Algebra Appl.*]{} [**522**]{} (2017) 140–152.]{}

T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, New York 1995.

Y. Kang. Hajós-like theorem for signed graphs. [[*European J Combin.*]{} [**67**]{} (2018) 199–207.]{}

D. Král. Hajós’ theorem for list coloring. [[**]{} [**287**]{} (2004) 161–163.]{}

A. J. Mansfield and D. J. A. Welsh. Some coloring problems and their complexity. [[*Ann. Discrete Math.*]{} [**13**]{} (1982) 159-170.]{}

B. Mohar. Hajós theorem for coloring of edge weighted graphs. [[*Combinatorica*]{} [**25**]{} (2004) 65–76.]{}

B. Mohar. Eigenvalues and colorings of digraphs. [[*Linear Algebra and its Applications*]{} [**432**]{} (2010) 2273–2277.]{}

M. Molloy. Chromatic neighborhood set. [[*J Graph Theory*]{} [**31**]{} (1999) 303–311.]{}

J. Nešetril. The homomorphism structure of classes of graphs. [[*Combin. Probab. Comput.*]{} [**8**]{} (1999) 177–184.]{}

V. Neumann-Lara. The dichromatic number of a digraph. [[**]{} [**33**]{} (1982) 265–270.]{}

V. Neumann-Lara. The $3$- and $4$-chromatic tournaments of minimum order. [[*Discrete Math.*]{} [**135**]{} (1994) 233–243.]{} Ø. Ore. The Four Color Problem. Academic Press, New York 1967.

T. Pitassi and A. Urquhart. The complexity of the Hajós calculus. [[*SIAM J Discrete Math.*]{} [**8**]{} (1995) 464–483.]{}

T. Schweser and M. Stiebitz. Degree choosable signed graphs. [[**]{} [**350**]{} (2017) 882–891.]{} M. Stehlík. Critical graphs with connected complements. [[**]{} [**89**]{} (2003) 189–194.]{}

A. Urquhart. The graph constructions of Haj[ó]{}s and Ore. [[*J Graph Theory*]{} [**26**]{} (1997) 211–215.]{}

X. Zhu. An analogue of Hajós’ theorem for circular chromatic number II. [[*Graphs Combin.*]{} [**265**]{} (2003) 419–432.]{}

[^1]: Research supported by the Danish research council under grant number 7014-00037B

[^2]: University of Southern Denmark, IMADA, Campusvej 55, DK-5320 Odense M, Denmark. E-mail address: jbj@imada.sdu.dk

[^3]: University of Southern Denmark, IMADA, Campusvej 55, DK-5320 Odense M, Denmark. E-mail address: bellitto@imada.sdu.dk

[^4]: Technische Universität Ilmenau, Inst. of Math., PF 100565, D-98684 Ilmenau, Germany. E-mail address: thomas.schweser@tu-ilmenau.de

[^5]: Technische Universität Ilmenau, Inst. of Math., PF 100565, D-98684 Ilmenau, Germany. E-mail address: michael.stiebitz@tu-ilmenau.de
