# Measurable Brooks’s Theorem for Directed Graphs

Cecelia Higgins

(Date: April 10, 2024)

###### Abstract.

We prove a descriptive version of Brooks’s theorem for directed graphs. In
particular, we show that, if $D$ is a Borel directed graph on a standard Borel
space $X$ such that the maximum degree of each vertex is at most $d\geq 3$,
then unless $D$ contains the complete symmetric directed graph on $d+1$
vertices, $D$ admits a $\mu$-measurable $d$-dicoloring with respect to any
Borel probability measure $\mu$ on $X$, and $D$ admits a $\tau$-Baire-
measurable $d$-dicoloring with respect to any Polish topology $\tau$
compatible with the Borel structure on $X$. We also prove a definable version
of Gallai’s theorem on list dicolorings for directed graphs by showing that
any Borel directed graph of bounded degree whose connected components are not
Gallai trees is Borel degree-list-dicolorable.

##  1\. Introduction

A classical graph theory result states that, for a finite undirected graph $G$
such that each vertex has degree at most $d$, there is a proper
$(d+1)$-coloring of $G$. The proof is a simple greedy algorithm argument; each
vertex receives the first color that has not already been assigned to any of
its neighbors. It is easy to see that this upper bound is sharp: For $d=2$, if
$G$ is an odd cycle, then each vertex of $G$ has degree $2$, but the chromatic
number of $G$ is $3$; for $d\geq 3$, if $G$ is the complete graph on $d+1$
vertices, then each vertex of $G$ has degree $d$, but the chromatic number of
$G$ is $d+1$.

However, these obvious obstructions to a smaller upper bound on the chromatic
number are the only obstructions. A 1941 theorem of Brooks characterizes the
graphs such that each vertex has degree at most $d$ which have proper
$d$-colorings as exactly the graphs which do not contain odd cycles or
complete graphs.

######  Theorem 1.1 ([Bro41]).

Let $G$ be a finite undirected graph such that each vertex has degree at most
$d$. If $d=2$, assume $G$ has no odd cycles; if $d\geq 3$, assume $G$ does not
contain the complete graph on $d+1$ vertices. Then there is a proper
$d$-coloring of $G$.

Suppose we wish to impose an additional requirement on the proper coloring:
Consider a function $L$ which assigns to each vertex $x$ of $G$ a list $L(x)$
of colors. An $L$-list-coloring of $G$ is a proper coloring $c$ of $G$ such
that $c(x)\in L(x)$ for all vertices $x$ of $G$. We say that $G$ is degree-
list-colorable if, for any function $L$ such that $|L(x)|\geq\deg(x)$ for all
vertices $x$, there is an $L$-list coloring of $G$. Note that, when
$L(x)=\\{0,1,\dots,d-1\\}$ for all vertices $x$ of $G$, then $G$ is $L$-list-
colorable if and only if $G$ has a proper $d$-coloring.

Recall that a set $S$ of vertices of $G$ is biconnected if the induced
subgraph $G[S]$ of $G$ is connected and the induced subgraphs
$G[S\setminus\\{s\\}]$ are connected for each $s\in S$. A block in $G$ is a
maximal biconnected set of vertices of $G$. A Gallai tree is a connected graph
in which each block induces either an odd cycle or a complete graph. Results
obtained independently by Borodin and Erdős, Rubin, and Taylor characterize
the finite undirected graphs which are degree-list-colorable as the graphs
whose connected components are not Gallai trees. The following theorem is
typically referred to as Gallai’s theorem.

######  Theorem 1.2 ([Bor77], [ERT79]).

Let $G$ be a finite undirected graph. Then $G$ is degree-list-colorable if and
only if no connected component of $G$ is a Gallai tree.

Brooks’s proof of Theorem 1.1 and the proofs of Borodin and Erdős, Rubin, and
Taylor of Theorem 1.2 all use classical techniques and do not immediately
generalize to the descriptive setting. Indeed, results of Marks ([Mar16])
demonstrate that Brooks’s theorem fails in the Borel context; in particular,
Marks constructs, for each $d$, a Borel acyclic $d$-regular graph whose Borel
chromatic number is $d+1$ ([Mar16], Theorem 1.3). However, in 2016, Conley,
Marks, and Tucker-Drob gave both a measurable version of Brooks’s theorem and
a definable version of Gallai’s theorem.

######  Theorem 1.3 ([CMT16], Theorem 1.2).

Let $G$ be an undirected Borel graph on a standard Borel space $X$ such that
each vertex has degree at most $d\geq 3$. Assume $G$ does not contain the
complete graph on $d+1$ vertices. Then:

  1. (1)

For any Borel probability measure $\mu$ on $X$, there is a $\mu$-measurable
proper $d$-coloring of $G$.

  2. (2)

For any Polish topology $\tau$ compatible with the Borel structure on $X$,
there is a $\tau$-Baire-measurable proper $d$-coloring of $G$.

######  Theorem 1.4 ([CMT16], Theorem 1.4).

Let $G$ be a locally finite undirected Borel graph on a standard Borel space
$X$. Assume that no connected component of $G$ is a Gallai tree. Then $G$ is
Borel degree-list-colorable.

In this paper, we show that the two theorems above have analogues for directed
graphs (or digraphs), in which each edge between vertices has an orientation.
The coloring problem of interest in the digraph setting is the problem of
producing a dicoloring, an assignment of colors to vertices so that no
directed cycle, that is, a sequence $(x_{0},x_{1},\dots,x_{k}=x_{0})$ of
vertices in which $x_{i}$ has an out-oriented edge to $x_{i+1}$ for each
$i<d$, is monochromatic. The notion of dicoloring was introduced first by
Neumann-Lara ([NL82]) in 1982 and again by Mohar ([Moh03]) in 2003, and it has
since been studied extensively.

Consider a digraph $D$ such that each vertex has maximum degree at most $d$,
so that each vertex has at most $d$ out-oriented neighbors and at most $d$ in-
oriented neighbors. Then a simple greedy algorithm argument demonstrates that
the dichromatic number of $D$, which is the least number of colors needed to
produce a dicoloring of $D$, is less than or equal to $d+1$ (see [AA22] for a
complete proof). As in the undirected setting, this bound is sharp: For $d=1$,
if $D$ is a directed cycle, then the maximum degree of each vertex of $D$ is
$1$, but the dichromatic number of $D$ is 2; for $d=2$, if $D$ is the
symmetrization of an undirected odd cycle – that is, if $D$ is obtained by
replacing each edge of an undirected odd cycle with both an out-oriented edge
and an in-oriented edge – then each vertex of $D$ has maximum degree $2$, but
the dichromatic number of $D$ is $3$; and for $d\geq 3$, if $D$ is the
symmetrization of the complete graph on $d+1$ vertices, then each vertex of
$D$ has maximum degree $d$, but the dichromatic number of $D$ is $d+1$.

The following theorem, which was first stated by Mohar in 2010 and later
proved in full by Harutyunyan and Mohar in 2011, parallels Brooks’s theorem by
characterizing the obstructions to having a smaller upper bound on the
dichromatic number.

######  Theorem 1.5 ([Moh10], Theorem 2.3; [HM11]).

Let $D$ be a finite directed graph such that each vertex has maximum degree at
most $d$. If $d=1$, assume $D$ has no directed cycles; if $d=2$, assume $D$
does not contain the symmetrization of any undirected odd cycles; and if
$d\geq 3$, assume $D$ does not contain the symmetrization of the undirected
complete graph on $d+1$ vertices. Then there is a $d$-dicoloring of $D$.

This theorem does not hold in the Borel setting; by symmetrizing the
$d$-regular acyclic undirected graphs with Borel chromatic number $d+1$
constructed by Marks in [Mar16], we obtain digraphs in which each vertex has
maximum degree $d$ and which do not contain large complete digraphs but which
have no Borel $d$-dicolorings. However, this theorem does hold in the
measurable setting. Our main result is the following.

######  Theorem 1.6.

Let $D$ be a Borel directed graph on a standard Borel space $X$. Suppose there
is $d\geq 3$ such that the maximum degree of $x$ is at most $d$ for all $x\in
X$, and assume $D$ does not contain the symmetrization of the undirected
complete graph on $d+1$ vertices. Then:

  1. (1)

For any Borel probability measure $\mu$ on $X$, there is a $\mu$-measurable
$d$-dicoloring of $D$.

  2. (2)

For any Polish topology $\tau$ compatible with the Borel structure on $X$,
there is a $\tau$-Baire-measurable $d$-dicoloring of $D$.

Also in 2011, Harutyunyan and Mohar proved a digraph version of Gallai’s
theorem. If $L$ is a function which assigns to each vertex $x$ of $D$ a list
$L(x)$ of colors, then an $L$-list-dicoloring of $D$ is a dicoloring $c$ of
$D$ such that $c(x)\in L(x)$ for all vertices $x$. We say that $D$ is degree-
list-dicolorable if, for any function $L$ such that $|L(x)|$ is greater than
or equal to the maximum degree of $x$ for all vertices $x$ of $D$, there is an
$L$-list-dicoloring of $D$. In the digraph context, a Gallai tree is a
connected digraph each of whose blocks induces a dicycle, the symmetrization
of an undirected odd cycle, or the symmetrization of an undirected complete
graph. A digraph is then degree-list-dicolorable if none of its connected
components is a Gallai tree.

######  Theorem 1.7 ([HM11], Theorem 2.1).

Let $D$ be a finite directed graph. If no connected component of $D$ is a
Gallai tree, then $D$ is degree-list-dicolorable.

We prove the following definable version of this result for digraphs of
bounded degree.

######  Theorem 1.8.

Let $D$ be a Borel directed graph of bounded degree on a standard Borel space
$X$. Assume that no connected component of $D$ is a Gallai tree. Then $D$ is
Borel degree-list-dicolorable.

In future work, we would like to better understand the implications of this
result for descriptive digraph combinatorics more generally. In particular,
although the problem of producing a dicoloring is not a locally checkable
labeling problem in general, we are interested in studying possible
connections between descriptive digraph combinatorics and LOCAL algorithms;
this may lead to extensions of Bernshteyn’s work ([Ber23]). We also consider
potential applications to a question about hypergraph colorings.

##  2\. Preliminaries

We begin by recalling the basic terminology and notation for directed graphs,
some of which was mentioned already in the introduction. A directed graph (or
digraph) $D$ is a pair $D=(X,A)$, where $X$ is a set, called the vertex set,
and $A\subseteq X^{2}$ is an irreflexive relation. The elements of $A$ are
called arcs.

Throughout the rest of this section, let $D=(X,A)$ be a directed graph on a
set $X$. Let $x\in X$. An element $y\in X$ is an out-neighbor of $x$ if there
is an arc from $x$ to $y$. The set of out-neighbors of $x$ is denoted
$N^{+}(x)$. An element $y\in X$ is an in-neighbor of $x$ if there is an arc
from $y$ to $x$. The set of in-neighbors of $x$ is denoted $N^{-}(x)$.

The out-degree of $x$, denoted $d^{+}(x)$, is defined by
$d^{+}(x)=|N^{+}(x)|$. The in-degree of $x$, denoted $d^{-}(x)$, is defined by
$d^{-}(x)=|N^{-}(x)|$. The maximum degree of $x$, denoted $d^{\max}(x)$, is
defined by $d^{\max}(x)=\max\\{d^{+}(x),d^{-}(x)\\}$. The minimum degree of
$x$, denoted $d^{\min}(x)$, is defined by
$d^{\min}(x)=\min\\{d^{+}(x),d^{-}(x)\\}$. Note that it is possible that
$N^{+}(x)\cap N^{-}(x)\neq\emptyset$.

The maximum side of $x$, denoted $N^{\max}(x)$, is defined by
$N^{\max}(x)=N^{+}(x)$ if $|N^{+}(x)|\geq|N^{-}(x)|$ and
$N^{\max}(x)=N^{-}(x)$ otherwise. The minimum side of $x$, denoted
$N^{\min}(x)$, is defined by $N^{\min}(x)=N^{+}(x)$ if
$|N^{+}(x)|\leq|N^{-}(x)|$ and $N^{\min}(x)=N^{-}(x)$ otherwise.

Let $D^{\prime}=(X^{\prime},A^{\prime})$ be a sub-digraph of $D$, that is, a
digraph such that $X^{\prime}\subseteq X$ and $A^{\prime}\subseteq A$. Then
for each $x\in A^{\prime}$, we write $d^{+}_{D^{\prime}}(x)$ for the out-
degree of $x$ in $D^{\prime}$, $d^{-}_{D^{\prime}}(x)$ for the in-degree of
$x$ in $D^{\prime}$, $d^{\max}_{D^{\prime}}(x)$ for the maximum degree of $x$
in $D^{\prime}$, and $d^{\min}_{D^{\prime}}(x)$ for the minimum degree of $x$
in $D^{\prime}$.

A directed cycle (or dicycle) in $D$ is a set $C=(x_{0},x_{1},\dots,x_{k})$ of
vertices of $D$ such that $x_{0}=x_{k}$, there is an arc from $x_{i}$ to
$x_{i+1}$ for each $i<k$, and $x_{i}\neq x_{j}$ for all $i,j<k$ with $i\neq
j$. If $k=2$, then $C$ is called a digon. A $d$-dicoloring of $D$ is a
function $c:X\rightarrow\\{0,1,\dots,d-1\\}$ such that, for any dicycle $C$ in
$D$, there are points $x,x^{\prime}\in C$ such that $c(x)\neq c(x^{\prime})$.
The dichromatic number of $D$, denoted $\overrightarrow{\chi}(D)$, is the
least $d\in\mathbb{N}$ such that there is a $d$-dicoloring of $D$.

Let $Y$ be a set, and let $[Y]^{<\infty}$ denote the collection of finite
subsets of $Y$. A ($Y$-)list assignment is a function
$L:X\rightarrow[Y]^{<\infty}$. Then $D$ is $L$-(list-)dicolorable if there is
a dicoloring $c$ of $D$ such that $c(x)\in L(x)$ for each $x\in X$. We say
that $D$ is degree-list-dicolorable if, for each list assignment $L$ such that
$|L(x)|\geq d^{\max}(x)$ for all $x\in X$, $D$ is $L$-dicolorable, and we say
that $D$ is (degree-plus-one)-list-dicolorable if, for each list assignment
$L$ such that $|L(x)|>d^{\max}(x)$ for all $x\in X$, $D$ is $L$-dicolorable.

Given an undirected graph $G$, we may replace each edge of $G$ with a digon to
obtain a directed graph. Precisely, the digraph $D=(X,A)$ is the
symmetrization of the undirected graph $G=(X,E)$ if, for all $x,y\in X$,
$\\{x,y\\}\in E$ if and only if $(x,y)\in A$ and $(y,x)\in A$. Note that, if
$D$ is the symmetrization of $G$, then $\overrightarrow{\chi}(D)=\chi(G)$. The
digraph $D$ is a symmetric cycle if $D$ is the symmetrization of an undirected
cyclic graph. The graph $D$ is a complete symmetric digraph if it is the
symmetrization of an undirected complete graph.

Conversely, by forgetting the orientations of the arcs in $D$, we obtain an
undirected graph, called the underlying graph $\tilde{D}$ of $D$. The vertex
set of $\tilde{D}$ is $X$, and two vertices $x,y\in X$ are adjacent in
$\tilde{D}$ if and only if either $(x,y)\in A$ or $(y,x)\in A$.

Many definitions from the theory of undirected graphs may now be imported to
the digraph context. In particular, we say that $D$ is locally finite if
$\tilde{D}$ is locally finite, $D$ is locally countable if $\tilde{D}$ is
locally countable, and $D$ is of bounded degree if $\tilde{D}$ is of bounded
degree. Also, we say $D$ is connected if $\tilde{D}$ is connected. If
$S\subseteq X$ and $|S|\geq 2$, then $S$ is biconnected if the induced sub-
digraph $\tilde{D}[S]$ is connected and the induced sub-digraphs
$\tilde{D}[S\setminus\\{s\\}]$ are connected for all $s\in S$. A block in $D$
is a maximal biconnected set in $D$. A connected component $C$ of $D$ is a
Gallai tree if each block in $D[C]$ induces a dicycle, a (finite) odd
symmetric cycle, or a (finite) complete symmetric digraph.

Throughout, we consider descriptive versions of the combinatorial notions for
digraphs. For the fundamentals of descriptive set theory, we refer the reader
to [Kec95].

######  Definition 2.1.

Let $X$ be a standard Borel space. A Borel digraph on $X$ is a digraph
$D=(X,A)$, where $A$ is Borel in the product topology on $X^{2}$. If $Y$ is a
Polish space, then a dicoloring $c:X\rightarrow Y$ of $D$ is a Borel
dicoloring if $c$ is a Borel function. The Borel dichromatic number of $D$,
denoted $\overrightarrow{\chi}_{B}(D)$, is the least $d\in\mathbb{N}$ such
that there is a Borel $d$-dicoloring of $D$.

A Borel ($Y$-)list assignment is a Borel function
$L:X\rightarrow[Y]^{<\infty}$. We say that $D$ is Borel degree-list-
dicolorable if, for any Borel list assignment $L$ such that $|L(x)|\geq
d^{\max}(x)$ for all $x\in X$, $D$ is Borel $L$-dicolorable. We say that $D$
is Borel (degree-plus-one)-list-dicolorable if, for any Borel list assignment
$L$ such that $|L(x)|>d^{\max}(x)$ for all $x\in X$, $D$ is Borel
$L$-dicolorable.

##  3\. Definable Digraph Combinatorics

In this section, we prove some initial results on the definable combinatorics
of digraphs. We show first that, if the minimum degree of each vertex in a
locally countable digraph is at most $d$, then the Borel dichromatic number is
at most $d+1$. The proof of the following proposition is similar to the proof
of Proposition 4.6 in [KST99].

######  Proposition 3.1.

Let $d\in\mathbb{N}$, and let $D$ be a locally countable Borel digraph on a
standard Borel space $X$. Suppose $d^{\min}(x)\leq d$ for all $x\in X$. Then
$\overrightarrow{\chi}_{B}(D)\leq d+1$.

###### Proof.

We proceed by induction on $d$. Suppose $d=0$; then $D$ has no dicycles, and
so clearly there is a Borel dicoloring of $D$ with just one color.

Now let $d\geq 0$. Assume that, for any locally countable Borel digraph
$D^{\prime}$ on a standard Borel space $X^{\prime}$, if $d^{\min}(x)\leq d$
for all $x\in X^{\prime}$, then $\overrightarrow{\chi}_{B}(D^{\prime})\leq
d+1$. Suppose now $d^{\min}(x)\leq d+1$ for all $x\in X$. Since the underlying
graph $\tilde{D}$ of $D$ is locally countable, it follows from Proposition 4.3
in [KST99] that there is a countable Borel proper coloring $c$ of $\tilde{D}$.
Now define $A_{0}=\\{x\in X:c(x)=0\\}$, and, having defined $A_{n}$, let
$A_{n+1}=\\{x\in X:c(x)=n+1\text{ and }N^{\min}(x)\cap(A_{0}\cup\cdots\cup
A_{n})=\emptyset\\}$. Write $A=\bigcup_{n\in\mathbb{N}}A_{n}$. Then $A$ is
Borel. We claim $A$ contains no dicycles. Otherwise, let
$C=(x_{0},x_{1},\dots,x_{k}=x_{0})$ be a dicycle in $A$. If $k=2$, then assume
without loss of generality that $c(x_{0})>c(x_{1})$. Then $N^{\min}(x_{0})\cap
A_{c(x_{1})}\neq\emptyset$, so that $x_{0}\notin A_{c(x_{0})}$, a
contradiction. If $k>2$, then let
$\alpha=\max\\{c(x_{0}),c(x_{1}),\dots,c(x_{k-1})\\}$. Then for some $i<k$,
$c(x_{i})=\alpha$. If $N^{\min}(x_{i})=N^{+}(x_{i})$, then since
$c(x_{i})>c(x_{i+1})$ and since $x_{i+1}\in A_{c(x_{i+1})}$, $x_{i}\notin
A_{c(x_{i})}$, a contradiction. Similarly, if $N^{\min}(x_{i})=N^{-}(x_{i})$,
then since $c(x_{i})>c(x_{i-1})$ and since $x_{i-1}\in A_{c(x_{i-1})}$,
$x_{i}\notin A_{c(x_{i})}$.

We claim also that, for each $x\in X$, either $x\in A$ or there is $y\in
N^{\min}(x)\cap A$. If $x\notin A$, then $x\notin A_{c(x)}$, so $c(x)>0$ and
$N^{\min}(x)\cap(A_{0}\cup\cdots\cup A_{c(x)-1})\neq\emptyset$. Therefore,
$d^{\min}_{D[X\setminus A]}(x)\leq d$. So by the inductive hypothesis, there
is a Borel dicoloring $c^{\prime}:(X\setminus A)\rightarrow\\{0,\dots,d\\}$ of
$D[X\setminus A]$. Now define a Borel dicoloring $c_{0}$ of $D$ by
$c_{0}(x)=c^{\prime}(x)$ if $x\in X\setminus A$ and $c_{0}(x)=d+1$ if $x\in
A$. ∎

We remark that, if the maximum degree of each vertex of $D$ is finite, then
$\tilde{D}$ is locally finite, and by Proposition 4.3 of [KST99], there is a
countable Borel proper coloring of $\tilde{D}$. Then clearly there is a
countable Borel dicoloring of $D$. Current work in progress of Raghavan and
Xiao ([RX23]) provides a dichotomy theorem characterizing which Borel digraphs
have countable Borel dicolorings. In particular, Raghavan and Xiao define a
canonical digraph – an analogue of the graph $\mathcal{G}_{0}$ ([KST99],
Definition 6.1) – and prove that the only digraphs which do not have countable
Borel dicolorings are those digraphs which admit continuous homomorphisms from
this canonical digraph.

Next, we show that any locally finite Borel digraph is Borel (degree-plus-
one)-list-dicolorable. For the proof, we first separate the vertex set of the
underlying graph into countably many independent sets $A_{0},A_{1},\dots$.
Then we list-dicolor the independent sets in order, beginning with $A_{0}$.
After we have list-dicolored $A_{0}\cup\cdots\cup A_{n}$, we update the list
assignments of each vertex $x\in A_{n+1}$ by removing the colors which appear
among both the out-neighbors and the in-neighbors of $x$.

######  Theorem 3.2.

Let $D$ be a locally finite Borel digraph on a standard Borel space $X$. Let
$Y$ be Polish, and let $L:X\rightarrow[Y]^{<\infty}$ be a Borel list
assignment such that $|L(x)|>d^{\max}(x)$ for all $x\in X$. Then $D$ has a
Borel $L$-dicoloring. In particular, $D$ is Borel (degree-plus-one)-list-
dicolorable.

###### Proof.

Since $\tilde{D}$ is locally finite, by Proposition 4.3 in [KST99], there is a
countable Borel proper coloring $c$ of $\tilde{D}$. For each $n\in\mathbb{N}$,
define $A_{n}=\\{x\in X:c(x)=n\\}$. Now let $<_{Y}$ be a Borel linear ordering
on $Y$, and define $c_{0}:A_{0}\rightarrow Y$ by letting $c_{0}(x)$ be the
$<_{Y}$-least element of $L(x)$ for each $x\in A_{0}$.

For each $i\in\mathbb{N}$, write $B_{i}=\bigcup_{j\leq i}A_{j}$. Let $n>0$,
and assume that, for each $i\leq n$, there are a list assignment
$L_{i}:A_{i}\rightarrow[Y]^{<\infty}$ and a Borel function
$c_{i}:B_{i}\rightarrow Y$ such that the following conditions obtain:

  * •

$L_{0}(x)=L(x)$ for all $x\in A_{0}$;

  * •

$c_{i}\restriction B_{j}=c_{j}$ for all $j<i$;

  * •

$c_{i}$ is a Borel $L$-dicoloring of $D[B_{i}]$;

  * •

$L_{i+1}(x)=L(x)\setminus\\{\alpha\in Y:\text{there exist }y,z\in B_{i}\text{
such that }y\in N^{+}(x),z\in N^{-}(x),\text{ and
}c_{i}(y)=c_{i}(z)=\alpha\\}$ for all $x\in A_{i+1}$; and

  * •

$|L_{i+1}(x)|>d^{\max}_{D[X\setminus B_{i}]}(x)$ for all $x\in A_{i+1}$.

We proceed to define a list assignment
$L_{n+1}:A_{n+1}\rightarrow[Y]^{<\infty}$ and a Borel function
$c_{n+1}:B_{n+1}\rightarrow Y$ such that:

  1. (1)

$c_{n+1}\restriction B_{i}=c_{i}$ for all $i\leq n$;

  2. (2)

$c_{n+1}$ is a Borel $L$-dicoloring of $D[B_{n+1}]$;

  3. (3)

$L_{n+1}(x)=L(x)\setminus\\{\alpha\in Y:\text{there exist }y,z\in B_{n}\text{
such that }y\in N^{+}(x),z\in N^{-}(x),\text{ and
}c_{n}(y)=c_{n}(z)=\alpha\\}$ for all $x\in A_{n+1}$; and

  4. (4)

$|L_{n+1}(x)|>d^{\max}_{D[X\setminus B_{n}]}(x)$ for all $x\in A_{n+1}$.

Let $x\in A_{n+1}$, and define $L_{n+1}(x)$ as in (3) above. Note that

$d^{\max}_{D[X\setminus B_{n}]}(x)=\max\\{d^{+}(x)-|N^{+}(x)\cap
B_{n}|,d^{-}(x)-|N^{-}(x)\cap B_{n}|\\}$

and that

$|L_{n+1}(x)|\geq|L(x)|-\min\\{|N^{+}(x)\cap B_{n}|,|N^{-}(x)\cap B_{n}|\\}.$

Without loss of generality, assume $\max\\{d^{+}(x)-|N^{+}(x)\cap
B_{n}|,d^{-}(x)-|N^{-}(x)\cap B_{n}|\\}=d^{+}(x)-|N^{+}(x)\cap B_{n}|$. Then

$\displaystyle d^{+}(x)-|N^{+}(x)\cap B_{n}|$ $\displaystyle\leq
d^{\max}(x)-|N^{+}(x)\cap B_{n}|$ $\displaystyle\leq|L(x)|-1-|N^{+}(x)\cap
B_{n}|$ $\displaystyle\leq|L(x)|-1-\min\\{|N^{+}(x)\cap B_{n}|,|N^{-}(x)\cap
B_{n}|\\}$ $\displaystyle\leq|L_{n+1}(x)|-1.$

So, $d^{\max}_{D[X\setminus B_{n}]}(x)<|L_{n+1}(x)|$. In particular,
$|L_{n+1}(x)|\geq 1$. Then for any $x\in B_{n+1}$, we may define
$c_{n+1}(x)=c_{n}(x)$ if $x\notin A_{n+1}$ and $c_{n+1}(x)=\alpha$, where
$\alpha$ is the $<_{Y}$-least element of $L_{n+1}(x)$, if $x\in A_{n+1}$. It
is then easy to check that conditions (1), (3), and (4) above are satisfied by
$L_{n+1}$ and $c_{n+1}$. To see that condition (2) is satisfied, assume for
contradiction that there is a $c_{n+1}$-monochromatic dicycle
$C=(x_{0},x_{1},\dots,x_{k}=x_{0})$ in $B_{n+1}$. If $k=2$, then without loss
of generality, assume $c(x_{0})>c(x_{1})$. Then $x_{1}\in N^{+}(x_{0})\cap
N^{-}(x_{0})\cap A_{c(x_{1})}$, so that $L_{c(x_{0})}(x_{0})$ does not contain
$c_{n+1}(x_{1})$, which is a contradiction since
$c_{n+1}(x_{0})=c_{n+1}(x_{1})$. If $k>2$, then there is $i<k$ such that
$c(x_{i})>c(x_{i-1})$ and $c(x_{i})>c(x_{i+1})$. Then if we set
$\alpha=c_{n+1}(x_{i-1})=c_{n+1}(x_{i+1})$, we have $\alpha\notin
L_{c(x_{i})}(x_{i})$, which is a contradiction since $c_{n+1}(x_{i})=\alpha$.

Now define $c^{\prime}:X\rightarrow Y$ by
$c^{\prime}=\bigcup_{n\in\mathbb{N}}c_{n}$. Then $c^{\prime}$ is a Borel
$L$-dicoloring of $D$. ∎

##  4\. Measurable Brooks’s Theorem for Dicolorings

In this section, we prove Theorem 1.6 and Theorem 1.8. First, recall from the
introduction that Brooks’s theorem for dicolorings does not hold in the Borel
context; the simplest counterexample is the symmetrization of a $d$-regular
acyclic undirected Borel graph that has no Borel proper $d$-coloring (see
Theorem 1.3 in [Mar16]). However, even the following holds. The construction
involves the directed Schreier graph of the free part of a particular group
action.

######  Proposition 4.1.

Let $d\geq 3$. Then there is a Borel digraph $D$ on a standard Borel space $X$
such that $d^{+}(x)=d^{-}(x)=d$ for all $x\in X$, $D$ has neither digons nor
odd cycles, and $D$ has no Borel $d$-dicoloring.

###### Proof.

Fix $d\geq 3$. For each $i<d$, let
$\Gamma_{i}=\mathbb{Z}/4\mathbb{Z}=\langle\gamma_{i}\mathrel{|}\gamma_{i}^{4}=1\rangle$.
Let $X=(2^{\mathbb{N}})^{\Gamma_{0}*\cdots*\Gamma_{d-1}}$, and consider the
left shift action $a:\Gamma_{0}*\cdots*\Gamma_{d-1}\curvearrowright X$ defined
by

$(\alpha\cdot x)(\beta)=x(\alpha^{-1}\beta)$

for all $\alpha,\beta\in\Gamma_{0}*\cdots*\Gamma_{d-1},x\in X$. Define a Borel
digraph $D$ on $\text{Free}(X)$ by directing an arc from $x\in\text{Free}(X)$
to $y\in\text{Free}(X)$ if $x\neq y$ and $\gamma_{i}\cdot x=y$ for some $i<d$.
Then it is easy to see that $d^{+}(x)=d^{-}(x)=d$ for all $x\in\text{Free}(X)$
and that $D$ has neither digons nor odd cycles.

Assume for contradiction that there is a Borel $d$-dicoloring $c$ of $D$. For
each $i<d$, let $A_{i}=\\{x\in X:c(x)=i\\}$. Then the sets
$A_{0},A_{1},\dots,A_{d-1}$ form a Borel partition of $\text{Free}(X)$. By
Theorem 2.1 in [Mar17], there is $i<d$ such that, for some continuous
injection
$f:\text{Free}((2^{\mathbb{N}})^{\Gamma_{i}})\rightarrow\text{Free}(X)$, $f$
is equivariant under the left shift actions of $\Gamma_{i}$ on
$\text{Free}((2^{\mathbb{N}})^{\Gamma_{i}})$ and $\text{Free}(X)$ and
$\text{range}(f)\subseteq A_{i}$.

Now let $y\in\text{range}(f)$; then for some
$x\in\text{Free}((2^{\mathbb{N}})^{\Gamma_{i}})$, $f(x)=y$. Notice that
$(f(x),\gamma_{i}\cdot f(x),\gamma_{i}^{2}\cdot f(x),\gamma_{i}^{3}\cdot
f(x),f(x))$ is a directed cycle in $D$. However, since $f$ is
$\Gamma_{i}$-equivariant, we have $\gamma_{i}\cdot f(x)=f(\gamma_{i}\cdot x)$,
$\gamma_{i}^{2}\cdot f(x)=f(\gamma_{i}^{2}\cdot x)$, and $\gamma_{i}^{3}\cdot
f(x)=f(\gamma_{i}^{3}\cdot x)$. Then $f(x),\gamma_{i}\cdot
f(x),\gamma_{i}^{2}\cdot f(x),\gamma_{i}^{3}\cdot f(x)$ all belong to
$\text{range}(f)$ and hence to $A_{i}$, contradicting that $A_{i}$ contains no
dicycles. ∎

So, even a Borel digraph without digons may provide a counterexample to a
Borel version of Brooks’s theorem for directed graphs.

Now we turn to the measurable version of this theorem. The proofs of Theorems
1.6 and 1.8 rely heavily on the one-ended spanning forest technique developed
by Conley, Marks, and Tucker-Drob in [CMT16]. Recall that, if $f$ is a
function on a set $X$, then $f$ is one-ended if there is no sequence
$(x_{n})_{n\in\mathbb{N}}$ such that, for each $n\in\mathbb{N}$,
$f(x_{n+1})=x_{n}$. Note that one-ended functions do not have fixed points.

We first show that, if a digraph $D$ of bounded degree admits a Borel one-
ended function, then $D$ is Borel degree-list-dicolorable. The proof combines
the proof of Theorem 3.2 with the proof of Lemma 3.9 in [CMT16]: First, given
a Borel one-ended function $f$, we separate the graph into layers using the
ranks provided by $f$. Within each layer, we then construct a finite sequence
of sets that are independent in the underlying graph and that cover the entire
layer. Then we list-dicolor the independent sets in order, removing from the
list-assignment of each vertex in the subsequent independent set the colors
which appear already among both its out-neighbors and its in-neighbors.

######  Theorem 4.2.

Let $D$ be a Borel digraph of bounded degree on a standard Borel space $X$
with no isolated vertices, let $B\subseteq X$ be Borel, and let
$f:B\rightarrow X$ be a one-ended Borel function whose graph is contained in
$\tilde{D}$. Let $d\in\mathbb{N}$ be such that $d^{\max}(x)\leq d$ for all
$x\in X$. Let $Y$ be Polish, and let $L:X\rightarrow[Y]^{<\infty}$ be a Borel
list assignment such that $|L(x)|\geq d^{\max}(x)$ for all $x\in B$. Then
$D[B]$ has a Borel $L$-dicoloring. In particular, $D$ is Borel degree-list-
dicolorable.

###### Proof.

For each $n\in\mathbb{N}$, write $f^{n}[B]=\\{x\in X:\text{there exist
}x_{1},x_{2},\dots,x_{n}\in B\text{ such that }f(x_{1})=x\text{ and
}f(x_{i+1})=x_{i}\text{ for all $i<n$}\\}$. Let $B_{n}=B\cap(f^{n}[B]\setminus
f^{n+1}[B])$. Note that, if $n\neq m$, then $B_{n}\cap B_{m}=\emptyset$. We
claim that $B=\bigcup_{n\in\mathbb{N}}B_{n}$. Assume for contradiction that
there is $x\in B\setminus\bigcup_{n\in\mathbb{N}}B^{n}$. Then $x\in f^{n}[B]$
for all $n\in\mathbb{N}$. So the set $f^{-\mathbb{N}}(x)=\\{y\in B:\text{for
some $n\geq 1$, there are }x_{1},x_{2},\dots,x_{n-1}\in B\text{ such that
}f(x_{1})=x,f(x_{i+1})=x_{i}\text{ for all $i<n$, and }f(y)=x_{n-1}\\}$ is an
infinite, finitely branching tree with root $x$. By König’s lemma, there is an
infinite branch $(y_{n})_{n\in\mathbb{N}}$ through $f^{-\mathbb{N}}(x)$. Then
for each $n\in\mathbb{N}$, $f(y_{n+1})=y_{n}$, contradicting that $f$ is one-
ended.

We proceed to $L$-dicolor $B$ one layer at a time. First, we color $B_{0}$.
Note that $\tilde{D}[B_{0}]$ is an undirected graph in which each vertex has
degree at most $2d$, since $d^{\max}(x)\leq d$ for all $x\in B$. So, by
Proposition 4.2 in [KST99], there is a Borel maximal $\tilde{D}$-independent
set $B^{0}_{0}\subseteq B_{0}$. Now, let $0<i<2d-1$, and suppose
$B_{0}^{j}\subseteq B_{0}$ has been defined for each $j\leq i$ such that
$B_{0}^{j}$ is a Borel maximal $\tilde{D}$-independent set in
$B_{0}\setminus(B^{0}_{0}\cup B^{1}_{0}\cup\cdots\cup B^{j-1}_{0})$. Then let
$B^{i+1}_{0}$ be a Borel maximal $\tilde{D}$-independent set in
$B_{0}\setminus(B^{0}_{0}\cup B^{1}_{0}\cup\cdots\cup B^{i}_{0})$. Finally,
note that, if $x\in B_{0}\setminus(B^{0}_{0}\cup B^{1}_{0}\cup\cdots\cup
B^{2d-1}_{0})$, then $d^{\max}_{D[B_{0}\setminus(B^{0}_{0}\cup
B^{1}_{0}\cup\cdots\cup B^{2d-1}_{0})]}(x)=0$. Then
$B^{2d}_{0}=B_{0}\setminus(B^{0}_{0}\cup B^{1}_{0}\cup\cdots\cup
B^{2d-1}_{0})$ is a Borel $\tilde{D}$-independent set. For each $i\leq 2d$,
write $B^{<i}_{0}=\emptyset$ if $i=0$ and $B^{<i}_{0}=\bigcup_{j<i}B^{j}_{0}$
if $i>0$, and write $B^{\leq i}_{0}=\bigcup_{j\leq i}B^{j}_{0}$.

Now note that, for each $x\in B^{0}_{0}$, $d^{\max}_{D[B^{0}_{0}]}(x)=0$.
Since $D$ has no isolated vertices, and since $|L(x)|\geq d^{\max}_{D}(x)$ for
each $x\in X$, it follows that $|L(x)|\geq 1$ for each $x\in B^{0}_{0}$. So,
by Theorem 3.2, there is a Borel $L$-dicoloring $c^{0}_{0}$ of $D[B^{0}_{0}]$.
Now let $1\leq i<2d$, and suppose Borel $L$-dicolorings $c^{j}_{0}:B^{\leq
j}_{0}\rightarrow Y$ have been defined for all $j\leq i$ so that the following
conditions hold:

  * •

If $j^{\prime}<j$, then $c^{j}_{0}\restriction(B^{\leq
j^{\prime}}_{0})=c^{j^{\prime}}_{0}$; and

  * •

For any $1\leq j\leq i$ and for any $x\in B^{j}_{0}$, if $x$ has an out-
neighbor $y\in B^{<j}_{0}$ and an in-neighbor $z\in B^{<j}_{0}$ with
$\alpha=c^{j-1}_{0}(y)=c^{j-1}_{0}(z)$, then $c^{j}_{0}(x)\neq\alpha$.

Then for each $x\in B^{i+1}_{0}$, let

$L^{i+1}_{0}(x)=L(x)\setminus\\{\alpha\in Y:\text{there are }y,z\in B^{\leq
i}_{0}\text{ such that }c^{i}_{0}(y)=c^{i}_{0}(z)=\alpha\\}.$

Then, since $x$ has at least one neighbor, namely $f(x)$, not contained in
$B_{0}$, we have

$\displaystyle|L^{i+1}_{0}(x)|$ $\displaystyle\geq|L(x)|-(d^{\max}(x)-1)$
$\displaystyle\geq d^{\max}(x)-(d^{\max}(x)-1)$ $\displaystyle=1,$

so that $0=d^{\max}_{D[B^{i+1}_{0}]}(x)<|L^{i+1}_{0}(x)|$. Therefore, again by
Theorem 3.2, there is a Borel $L^{i+1}_{0}$-dicoloring $c$ of
$D[B^{i+1}_{0}]$. Define $c^{i+1}_{0}:B^{\leq i+1}_{0}\rightarrow Y$ by
$c^{i+1}_{0}(x)=c(x)$ if $x\in B^{i+1}_{0}$ and $c^{i+1}_{0}(x)=c^{i}_{0}(x)$
otherwise. Finally, define $c_{0}=c^{2d}_{0}$.

We now proceed to dicolor $B_{1}$. The procedure is similar to that for
dicoloring $B_{0}$; we construct $\tilde{D}$-independent sets
$B^{0}_{1},B^{1}_{1},\dots,B^{2d}_{1}$ as above and color one set at a time to
obtain a coloring $c_{1}$ of $D[B_{1}]$. However, in this case, if $x\in
B^{0}_{1}$, then

$\displaystyle L_{1}^{0}(x)=L(x)\setminus\\{\alpha\in Y:$
$\displaystyle\,\text{there exist }y,z\in B_{0}\text{ such that }y\in
N^{+}(x),z\in N^{-}(x),$ $\displaystyle\text{ and
}c_{0}(y)=c_{0}(z)=\alpha\\}.$

Then since $x$ has at least one neighbor, namely $f(x)$, not in $B_{1}$, we
have $0=d^{\max}_{D[B^{0}_{1}]}(x)<|L_{1}^{0}(x)|$, so that $D[B^{0}_{1}]$ may
be $L^{0}_{1}$-dicolored. The sets $B_{2},B_{3},\dots$ are dicolored similarly
by functions $c_{2},c_{3},\dots$.

Now let $c=\bigcup_{n\in\mathbb{N}}c_{n}$. Then $c$ is Borel. Assume for
contradiction that there is a $c$-monochromatic cycle
$C=(x_{0},x_{1},\dots,x_{k}=x_{0})$ in $D$. If $k=2$, then let
$n\in\mathbb{N}$ be maximal with $C\cap B_{n}\neq\emptyset$, and let $j\leq
2d$ be maximal with $C\cap B^{j}_{n}\neq\emptyset$. Without loss of
generality, suppose $x_{0}\in B^{j}_{n}$. Then $x_{1}\notin B^{j}_{n}$. So,
$c(x_{1})\notin L^{j}_{n}(x_{0})$, a contradiction since $c(x_{0})=c(x_{1})$.
If $k>2$, then again let $n\in\mathbb{N}$ be maximal with $C\cap
B_{n}\neq\emptyset$, and let $j\leq 2d$ be maximal with $C\cap
B^{j}_{n}\neq\emptyset$. Then there is $i\leq k$ such that $x_{i}\in
B^{j}_{n}$. It follows that $x_{i-1},x_{i+1}\notin B^{j}_{n}$. Then either
$x_{i-1}\in B_{m}$ for some $m<n$, or $x_{i-1}\in B^{j^{\prime}}_{n}$ for some
$j^{\prime}<j$, and similarly for $x_{i+1}$. In any case, it follows that
$\alpha=c(x_{i-1})=c(x_{i+1})$ is not an element of $L^{j}_{n}(x_{i})$, a
contradiction since $c(x_{i})=\alpha$. Thus, $c$ is a Borel $L$-dicoloring of
$D$. ∎

We will use the following proposition of Conley, Marks, and Tucker-Drob to
construct one-ended Borel functions. For a graph $G$ on a set $X$ and for
$A\subseteq X$, we use the notation $[A]_{G}$ to denote the set of all points
$x\in X$ such that $x$ has a path through $G$ to some point of $A$. For a
vertex $x$ of $G$, we write $[x]_{G}$ for $[\\{x\\}]_{G}$. Also, if $D$ is a
digraph, then we write $[A]_{D}$ for $[A]_{\tilde{D}}$.

######  Proposition 4.3 ([CMT16], Proposition 3.1).

Let $G$ be a locally finite Borel graph on a standard Borel space $X$, and let
$A\subseteq X$ be Borel. Then there is a one-ended Borel function
$f:([A]_{G}\setminus A)\rightarrow[A]_{G}$ whose graph is contained in $G$.

Our next step towards proving Theorem 1.6 is to show that digraphs of bounded
degree are Borel degree-list-dicolorable on connected components which contain
vertices whose minimum degree is smaller than the maximum degree. To construct
the dicoloring, we first reserve a set of small-minimum-degree vertices that
is independent in the underlying graph and dicolor the vertices outside of
this reserved set using a one-ended function. Then, since each reserved vertex
has small minimum degree, there is at least one color in its list of available
colors which does not appear among both the out-neighbors and the in-neighbors
of the vertex; then the initial dicoloring can be extended to this vertex. The
proof resembles the first part of the proof of Theorem 1.2 in [CMT16].

######  Proposition 4.4.

Let $D$ be a Borel digraph of bounded degree on a standard Borel space $X$,
and let $B=\\{x\in X:d^{\min}(x)<d^{\max}(x)\\}$. Then $D[[B]_{D}]$ is Borel
degree-list-dicolorable.

###### Proof.

Let $Y$ be Polish, and let $L:X\rightarrow[Y]^{<\infty}$ be a list assignment
such that $|L(x)|\geq d^{\max}(x)$ for each $x\in X$. Since $D$ is of bounded
degree, the underlying graph $\tilde{D}$ is also of bounded degree. Therefore,
by Proposition 4.2 in [KST99], there is a Borel maximal
$\tilde{D}$-independent set $B^{\prime}\subseteq B$. Since
$[B^{\prime}]_{D}=[B]_{D}$, by Proposition 4.3, there is a one-ended Borel
function $f:([B]_{D}\setminus B^{\prime})\rightarrow[B]_{D}$ whose graph is
contained in $\tilde{D}$. Then by Theorem 4.2, $D[[B]_{D}\setminus
B^{\prime}]$ has a Borel $L$-dicoloring.

Now we extend $c$ to a function $c^{\prime}:[B]_{D}\rightarrow Y$ by letting
$c^{\prime}(x)=c(x)$ if $x\notin B^{\prime}$; if $x\in B^{\prime}$, then let
$<_{Y}$ be a Borel linear ordering of $Y$, and define $c^{\prime}(x)$ to be
the $<_{Y}$-least color $\alpha\in L(x)$ such that there are no $y\in
N^{+}(x)\cap([B]_{D}\setminus B^{\prime})$ and $z\in
N^{-}(x)\cap([B]_{D}\setminus B^{\prime})$ with $c(y)=c(z)=\alpha$. Such an
$\alpha$ exists since $d^{\min}(x)<d^{\max}(x)$, so that at most
$d^{\max}(x)-1$ colors from $L(x)$ appear in $c[N^{+}(x)]\cap c[N^{-}(x)]$.
Then $c^{\prime}$ is a Borel $L$-dicoloring of $D[[B]_{D}]$. ∎

From now on, we say that $D$ is Eulerian if, for each vertex, its in-degree
and out-degree are the same. So, the proposition above demonstrates that, if
$D$ is a bounded-degree Borel digraph that is not Eulerian, then $D$ is Borel
degree-list-dicolorable.

As a corollary to the proof of Proposition 4.4, we obtain the following.

######  Corollary 4.5.

Let $D$ be a Borel digraph on a standard Borel space $X$, and let $d$ be such
that $d^{\max}(x)\leq d$ for all $x\in X$. Let $B=\\{x\in X:d^{\min}(x)<d\\}$.
Then $D[[B]_{D}]$ is Borel $d$-dicolorable.

###### Proof.

Take $B^{\prime}$ and $c$ as in the proof of the previous proposition, and let
$L(x)=\\{0,1,\dots,d-1\\}$ for all $x\in X$. Then extend $c$ to a function
$c^{\prime}$ on $X$ by setting $c^{\prime}(x)=c(x)$ for all $x\notin
B^{\prime}$; for each $x\in B^{\prime}$, let $c^{\prime}(x)=\alpha$, where
$\alpha$ is the least color such that $\alpha$ does not belong to both
$N^{+}(x)\cap([B]_{D}\setminus B^{\prime})$ and $N^{-}(x)\cap([B]_{D}\setminus
B^{\prime})$. Such an $\alpha$ exists since $d^{\min}(x)<d$. ∎

Next we work towards proving Theorem 1.8, which will be used in the proof of
Theorem 1.6. In particular, we show that digraphs of bounded degree are Borel
degree-list-dicolorable on connected components which are not Gallai trees.
The proof is similar to the proof of Theorem 4.1 in [CMT16]. The argument
again involves reserving a set $B^{\prime\prime}$ of points that belong to
biconnected sets which do not induce dicycles, odd symmetric cycles, or
complete symmetric digraphs and which are sufficiently well-separated in the
underlying graph. Once a degree-list-dicoloring $a$ of the points outside
$B^{\prime\prime}$ has been constructed, the points of $B^{\prime\prime}$ will
be colored in a two-step procedure: First, the values of $a$ are changed on
certain neighborhoods of the points in $B^{\prime\prime}$; then, the
dicoloring that results from changing $a$ on these neighborhoods will be
extended until all points are colored. The separation between the points of
$B^{\prime\prime}$ will guarantee that the alterations made to $a$ do not
interfere with one another.

The biconnected sets to which the points of $B^{\prime\prime}$ will belong
will be required to have the following form.

######  Definition 4.6.

Let $D$ be a digraph on a set $X$. Let
$G=(x_{0},x_{1},\dots,x_{k}=x_{0})\subseteq X$ be a cycle in $\tilde{D}$, so
that, for each $i<k$, $x_{i}$ is $\tilde{D}$-adjacent to $x_{i+1}$ and, for
all $i,j<k$, $x_{i}\neq x_{j}$ if $i\neq j$. Then $G$ is a good cycle if the
following two conditions hold:

  1. (1)

There is some orientation of the arcs in $G$ that does not yield a dicycle;
and

  2. (2)

$D[G]$ is not an odd symmetric cycle or a complete symmetric digraph.

The following proposition can be deduced from the proof of Lemma 2.1 in
[HM11]. It shows that any “good” biconnected set of size at least $3$ contains
a good cycle.

######  Proposition 4.7 ([HM11]).

Let $D$ be an Eulerian digraph on a set $X$, and let $M\subseteq X$ be a
finite biconnected set in $D$ such that $|M|\geq 3$ and $M$ does not induce a
dicycle, an odd symmetric cycle, or a complete symmetric digraph. Then there
is a good cycle contained in $M$.

Consider an Eulerian digraph $D$. Let $L$ be a list assignment such that
$|L(x)|\geq d^{\max}(x)$ for all vertices $x$, and assume that all vertices of
$D$ except one vertex $x_{0}$ have been $L$-dicolored according to a function
$c$. If $|L(x_{0})|>d$, or if $|L(x_{0})|=d$ and the number of colors in
$L(x_{0})$ that appear among both the in-neighbors and the out-neighbors of
$x_{0}$ is less than $d$, then the coloring $c$ may be extended to $x_{0}$ by
defining $c(x_{0})$ to be the least color in $L(x_{0})$ which does not appear
among both the out-neighbors and the in-neighbors of $x_{0}$. Otherwise, the
following proposition of Harutyunyan and Mohar shows that, by uncoloring any
neighbor $y$ of $x_{0}$ and then coloring $x_{0}$ with the color that $y$
previously had, we obtain a new $L$-dicoloring $c^{\prime}$ of
$D[X\setminus\\{y\\}]$.

######  Proposition 4.8 ([HM11], Lemma 2.2).

Let $D$ be an Eulerian digraph on a set $X$, and let $L$ be a list assignment
such that $|L(x)|\geq d^{\max}(x)$ for all $x\in X$. Let $x_{0}\in X$, and
suppose $c$ is an $L$-dicoloring of $D[X\setminus\\{x_{0}\\}]$ such that, for
each $\alpha\in L(x_{0})$, $x_{0}$ has both an out-neighbor and an in-neighbor
of color $\alpha$. Let $y$ be a neighbor of $x_{0}$, and define $c^{\prime}$
on $X\setminus\\{y\\}$ by $c^{\prime}(x_{0})=c(y)$ and $c^{\prime}(z)=c(z)$ if
$z\neq x_{0}$. Then $c^{\prime}$ is an $L$-dicoloring of
$D[X\setminus\\{y\\}]$.

The final result that we need before proving Theorem 1.8 can be deduced from
Lemmas 2.4 and 2.5 in [HM11]. It shows that, if $G$ is a good cycle and all
vertices of $D$ except one vertex in $G$ have been $L$-dicolored, then by
repeatedly uncoloring and then coloring pairwise adjacent vertices in $G$ as
in the statement of Proposition 4.8, we reach a vertex $y\in G$ for which some
element of $L(y)$ does not appear among both the out-neighbors and the in-
neighbors of $y$. At this stage, the $L$-dicoloring may be extended to $y$.

######  Proposition 4.9 ([HM11]).

Let $D$ be an Eulerian digraph on a set $X$, and let $L$ be a list assignment
for $D$ such that $|L(x)|\geq d^{\max}(x)$ for all $x\in X$. Let $G\subseteq
X$ be a good cycle. Let $x\in G$, and suppose that there is an $L$-dicoloring
$a$ of $D[X\setminus\\{x\\}]$. Then there are a sequence
$(x=x_{0},x_{1},\dots,x_{k})$ of vertices in $G$ and a sequence
$(a=a_{0},a_{1},\dots,a_{k})$ of functions such that, for each $i<k$:

  1. (1)

$x_{i}$ is $\tilde{D}$-adjacent to $x_{i+1}$;

  2. (2)

$a_{i}$ is an $L$-dicoloring of $D[X\setminus\\{x_{i}\\}]$, and $a_{k}$ is an
$L$-dicoloring of $D[X\setminus\\{x_{k}\\}]$;

  3. (3)

For each $\alpha\in L(x_{i})$, $\alpha\in a_{i}[N^{-}(x_{i})]\cap
a_{i}[N^{+}(x_{i})]$;

  4. (4)

$a_{i+1}$ is obtained from $a_{i}$ by uncoloring $x_{i+1}$ and coloring
$x_{i}$ with $a_{i}(x_{i+1})$ (i.e., through an application of Proposition
4.8); and

  5. (5)

There is some color $\alpha\in L(x_{k})$ such that either $\alpha\notin
a_{k}[N^{-}(x_{k})]$ or $\alpha\notin a_{k}[N^{+}(x_{k})]$.

Finally, recall that the boundary of a set $S$ in the digraph $D=(X,A)$,
denoted $\partial S$, is the set $\partial S=\\{x\in X:x\notin S\text{ but
there exists $y\in S$ such that $x\mathrel{\tilde{D}}y$}\\}$.

Now we prove Theorem 1.8. We restate the theorem here for convenience.

######  Theorem 4.10.

Let $D$ be a Borel digraph of bounded degree on a standard Borel space $X$.
Let $L$ be a Borel list assignment for $D$ such that $|L(x)|\geq d^{\max}(x)$
for all $x\in X$, and let $B=\\{x\in X:D[[x]_{D}]\text{ is not a Gallai
tree}\\}$. Then $D[B]$ has a Borel $L$-dicoloring. That is, $D[B]$ is Borel
degree-list-dicolorable.

###### Proof.

Note that, by Theorem 4.4, we may assume that $d^{\max}(x)=d^{\min}(x)$ for
all $x\in X$, that is, that $D$ is Eulerian.

Throughout the proof, fix $d\in\mathbb{N}$ such that $d^{\max}(x)\leq d$ for
all $x\in X$. Also, we shall call a biconnected set $S$ bad if the sub-digraph
that $S$ induces is a dicycle, an odd symmetric cycle, or a complete symmetric
digraph. For technical reasons, we assume first that each block of $D[B]$
which is not bad has cardinality at least $3$. We shall explain at the end of
the proof that there is a Borel $L$-dicoloring of the connected components of
$D[B]$ which have non-digon blocks of cardinality $2$.

Let

$[E_{D}]^{<\infty}=\\{S\in[X]^{<\infty}:\text{$S$ is contained in a connected
component of $D$}\\},$

and let

$\displaystyle A=\\{S\in[E_{D}]^{<\infty}:$ each connected component of $D[S]$
contains a block of $\displaystyle\,\text{cardinality at least $3$ which is
not bad}\\}.$

Define $G_{I}$ to be the intersection graph on $[E_{D}]^{<\infty}$, so that
$S,T\in[E_{D}]^{<\infty}$ are $G_{I}$-adjacent if and only if $S\neq T$ and
$S\cap T\neq\emptyset$. Then by Proposition 2 of [CM16], there is a countable
Borel proper coloring $c_{I}$ of $G_{I}$. Let now

$\displaystyle A^{\prime}=\\{S\in A:$ $\displaystyle\,c_{I}(S\cup\partial
S)\leq c_{I}(T\cup\partial T)\text{ for all $T\in A$}$
$\displaystyle\,\text{in the same $D$-component as $S$}\\},$

and define $B^{\prime}=\bigcup A^{\prime}$.

We next prove several claims about $B^{\prime}$. First, we need the following.

Claim 1. Let $x\in X$. Then $D[[x]_{D}]$ is not a Gallai tree if and only if
there is a finite connected set $T\subseteq[x]_{D}$ such that the induced sub-
digraph $D[T]$ contains a block of cardinality at least $3$ which is not bad.

Proof of Claim 1. ($\Rightarrow$) Suppose $D[[x]_{D}]$ is not a Gallai tree.
Then there is a block in $[x]_{D}$ that does not induce a dicycle, an odd
symmetric cycle, or a complete symmetric digraph. If there is a finite such
block $M$ in $[x]_{D}$, then since $M$ has cardinality at least $3$ by the
assumption at the beginning of the proof, we may take $T=M$ in the statement
of the claim.

Otherwise, there is an infinite block $M$ in $[x]_{D}$. Now we take
inspiration from the proof of Lemma 2.1 in [HM11]. Let $y,z\in M$ be such that
$d(y,z)\geq d+2$; such $y,z$ exist because $M$ is an infinite connected subset
of a locally finite graph. Since $M$ is biconnected, it follows from a
classical result of Whitney ([Whi32a], [Whi32b]) that there are two
internally-vertex-disjoint paths $P_{0},P_{1}$ from $y$ to $z$. Note that each
of $P_{0},P_{1}$ has length at least $d+2$. Again since the
$(d+2)$-neighborhood of $P_{0}\cup P_{1}$ is a finite set in a locally finite
graph, there is some $v\in M$ such that $d(v,P_{0}\cup P_{1})\geq d+2$. Since
$M$ is connected, there is a path $Q=(y=q_{0},q_{1},\dots,q_{k}=v)$ through
$M$ from $y$ to $v$.

Case 1: $Q$ contains some point of $P_{0}\cup P_{1}$ besides $y$. Let $i<k$ be
maximal such that $q_{i}\neq y$ and $q_{i}\in P_{0}\cup P_{1}$, and write
$y^{\prime}=q_{i}$. Since $M$ is biconnected, there is a path
$R=(y=r_{0},r_{1},\dots,r_{l}=v)$ through $M$ from $y$ to $v$ that is
internally-vertex-disjoint from $Q$. Let $j<l$ be maximal such that $r_{j}\in
P_{0}\cup P_{1}$, and write $y^{\prime\prime}=r_{j}$. Then
$y^{\prime},y^{\prime\prime}$ are distinct points of $P_{0}\cup P_{1}$, and
there are three internally-vertex-disjoint paths from $y^{\prime}$ to
$y^{\prime\prime}$: These are the two paths $S_{0},S_{1}$ arising from the
fact that $y^{\prime},y^{\prime\prime}$ are distinct points of the cycle
$P_{0}\cup P_{1}$, together with the concatenation $S_{2}$ of the sub-path of
$Q$ from $y^{\prime}$ to $v$ and the sub-path of $R$ from $v$ to
$y^{\prime\prime}$. Notice that the length of $S_{2}$ and the length of at
least one of $S_{0},S_{1}$ are at least $d+2$. So, two of the three paths
$S_{0},S_{1},S_{2}$ form a cycle $C$ of even length with cardinality at least
$d+2$. Since each vertex of $D$ has maximum degree at most $d$, the induced
sub-digraph $D[C]$ is not a complete symmetric digraph. So, if $D[C]$ is not a
dicycle, then we may take $T=C$ in the statement of Claim 1. If $D[C]$ is a
dicycle, then we may take $T=S_{0}\cup S_{1}\cup S_{2}$.

Case 2: The only point of $P_{0}\cup P_{1}$ in $Q$ is $y$. Again since $M$ is
connected, there is a path $R$ through $M$ from $z$ to $v$. If $R$ contains
some point of $P_{0}\cup P_{1}$ besides $z$, then we may proceed as in Case 1
by replacing $y$ with $z$ and $Q$ with $R$. Otherwise, there are three
internally-vertex-disjoint paths $P_{0},P_{1}$, and $R\cup Q$ (with
repetitions removed) between $y$ and $z$. Note that each of these paths has
length at least $d+2$. Then we may again proceed as in Case 1 by replacing
$S_{0},S_{1},S_{2}$ with $P_{0},P_{1},R\cup Q$.

($\Leftarrow$) Suppose there is a finite connected set $T\subseteq[x]_{D}$
such that $D[T]$ contains a block $M$ of size at least $3$ which is not bad.
If there is an infinite block in $[x]_{D}$ which contains $M$, then clearly
$D[[x]_{D}]$ is not a Gallai tree, and the proof is complete. If the only
blocks in $[x]_{D}$ which contain $M$ are finite, then since $M$ has
cardinality at least $3$, there is no block in $D$ containing $M$ that induces
a dicycle, an odd symmetric cycle, or a complete symmetric digraph. So
$D[[x]_{D}]$ is again not a Gallai tree. $\square$

Now we claim $B^{\prime}\subseteq B$. Let $x\in B^{\prime}$. Then there is
$S\in A^{\prime}$ such that $x\in S$. Because each connected component of
$D[S]$ contains a block of size at least $3$ which is not bad, it follows from
Claim 1 that $D[[x]_{D}]$ is not a Gallai tree. So $x\in B$. Furthermore,
Claim 1 implies that each connected component of $D[B]$ meets $B^{\prime}$.

Next, we show that each connected component of $D[B^{\prime}]$ is finite. Let
$x\in B^{\prime}$; then there is some $S\in A^{\prime}$ such that $x\in S$. We
claim $[x]_{D[B^{\prime}]}\subseteq(S\cup\partial S)$, which is a finite set.
Assume for contradiction that there is some $y\in B^{\prime}$ such that
$y\notin S\cup\partial S$, but there is a path $(x=x_{0},x_{1},\dots,x_{k}=y)$
through $\tilde{D}[B^{\prime}]$ from $x$ to $y$. Since $y\notin S\cup\partial
S$ and $x\in S$, there is $i<k$ such that $x_{i}\in\partial S$ and
$x_{i+1}\notin S\cup\partial S$. Let $T\in A^{\prime}$ be such that
$x_{i+1}\in T$. Then $(S\cup\partial S)\cap(T\cup\partial T)$ contains
$x_{i}$, so that $c_{I}(S\cup\partial S)\neq c_{I}(T\cup\partial T)$. This is
a contradiction since $S,T\in A^{\prime}$ belong to the same connected
component of $D$.

Note now that each connected component $C$ of $D[B^{\prime}]$ contains a
biconnected set $M$ of size at least $3$ that is not bad. Let $<_{X}$ be a
Borel linear ordering of $X$; then we define $M_{C}$ to be the
lexicographically least such $M$, assuming without loss of generality that the
elements of any finite subset of $X$ are listed in increasing order according
to $<_{X}$. Further, we may assume that, if $C,C^{\prime}$ are distinct
connected components of $D[B^{\prime}]$, then $M_{C}$ and $M_{C^{\prime}}$ are
such that $(M_{C}\cup\partial M_{C})\cap(M_{C^{\prime}}\cup\partial
M_{C^{\prime}})=\emptyset$; this is because, if $S\subseteq C$ and $T\subseteq
C^{\prime}$ are elements of $A^{\prime}$, then $S\cup\partial S\neq
T\cup\partial T$, so that $(S\cup\partial S)\cap(T\cup\partial T)=\emptyset$.

For each connected component $C$ of $D[B^{\prime}]$, by Proposition 4.7, there
is a good cycle $G$ in $M_{C}$; let $G_{C}$ be the lexicographically least
such cycle according to $<_{X}$, and let $x_{C}$ be the $<_{X}$-least element
of $G_{C}$. Finally, set $B^{\prime\prime}=\\{x\in X:\text{there is a
connected component $C$ of $D[B^{\prime}]$ such that }x=x_{C}\\}$. Then
$B^{\prime\prime}$ is Borel, and $[B^{\prime\prime}]_{D}=[B^{\prime}]_{D}=B$.

So, by Proposition 4.3, there is a one-ended Borel function from $(B\setminus
B^{\prime\prime})$ to $B$. Then by Theorem 4.2, there is a Borel
$L$-dicoloring $a$ of $D[B\setminus B^{\prime\prime}]$.

We proceed to define a Borel $L$-dicoloring $a^{\prime}$ of $D[B]$. For each
$x\in B^{\prime\prime}$, let $C$ be the connected component of $D[B^{\prime}]$
witnessing $x\in B^{\prime\prime}$, and let
$(x=x_{0},x_{1},\dots,x_{k}),(a=a_{0},a_{1},\dots,a_{k})$ be as in Proposition
4.9; this proposition may be applied since $G_{C}$ is a good cycle and
$x=x_{C}\in G_{C}$. Then the $L$-dicoloring $a_{k}$ may be extended to
$x_{k}$, since there is some color $\alpha\in L(x_{k})$ such that either
$\alpha\notin a_{k}[N^{-}(x_{k})]$ or $\alpha\notin a_{k}[N^{+}(x_{k})]$;
write $a_{C}$ for this extension of $a_{k}$. Then define
$a^{\prime}:B\rightarrow Y$ by $a^{\prime}(x)=a_{C}(x)$ if $x\in G_{C}$ and
$a^{\prime}(x)=a(x)$ if $x\notin G_{C}$ for any $C$.

We claim that $a^{\prime}$ is a dicoloring of $D[B]$. It is enough to show the
following.

Claim 2. Let $x,y\in B^{\prime\prime}$ be distinct. Let $c$ be a dicoloring of
$D[X\setminus\\{x,y\\}]$ such that, for each $\alpha\in L(x)$, $\alpha\in
c[N^{-}(x)]\cap c[N^{+}(x)]$, and for each $\beta\in L(y)$, $\beta\in
c[N^{-}(y)]\cap c[N^{+}(y)]$. Let $x^{\prime}$ be a neighbor of $x$, and let
$y^{\prime}$ be a neighbor of $y$. Then the function $c^{\prime}$ defined on
$X\setminus\\{x^{\prime},y^{\prime}\\}$ by $c^{\prime}(z)=c(z)$ if $z\neq
x,y$, $c^{\prime}(x)=c(x^{\prime})$, and $c^{\prime}(y)=c(y^{\prime})$ is an
$L$-dicoloring of $D[X\setminus\\{x^{\prime},y^{\prime}\\}]$.

Proof of Claim 2. Note first that, since $x,y\in B^{\prime\prime}$ are
distinct, then if $C,C^{\prime}$ are the connected components of $B^{\prime}$
witnessing that $x,y\in B^{\prime\prime}$, respectively, then
$(G_{C}\cup\partial G_{C})\cap(G_{C^{\prime}}\cup\partial
G_{C^{\prime}})=\emptyset$. Now assume for contradiction that there is a
$c^{\prime}$-monochromatic dicycle $K$. Then $K$ cannot contain $x^{\prime}$
or $y^{\prime}$, since these vertices are uncolored. Further, $K$ must contain
either $x$ or $y$; otherwise, there is a $c$-monochromatic dicycle,
contradicting that $c$ is a dicoloring. Suppose $x\in K$. Then
$c^{\prime}(x)=c(x^{\prime})$. Since, for each $\alpha\in L(x)$, $\alpha\in
c[N^{-}(x)]\cap c[N^{+}(x)]$, and since $(G_{C}\cup\partial
G_{C})\cap(G_{C^{\prime}}\cup\partial G_{C^{\prime}})=\emptyset$ so that $y$
and $y^{\prime}$ are not neighbors of $x$, it follows that there is exactly
one neighbor $z$ of $x$ such that $c^{\prime}(x)=c^{\prime}(z)$. Therefore,
any dicycle passing through $x$ either contains points of different colors or
contains an uncolored point. So, no dicycle containing $x$ is monochromatic. A
similar argument shows that no dicycle containing $y$ is monochromatic.
$\square$

This completes the proof in the case where each block of $D[B]$ that is not
bad has cardinality at least $3$. For the other case, let

$B_{0}=\\{x\in X:[x]_{D}\text{ has a non-digon block of cardinality $2$}\\}.$

As above, take a Borel set $A^{\prime}$ of non-digon blocks in $B_{0}$ such
that, if $M,M^{\prime}$ are elements of $A^{\prime}$ with $M\cup\partial M\neq
M^{\prime}\cup\partial M^{\prime}$, then $(M\cup\partial
M)\cap(M^{\prime}\cup\partial M^{\prime})=\emptyset$ and such that
$A^{\prime}$ meets each connected component of $D[B_{0}]$. Then set
$B^{\prime}=\bigcup A^{\prime}$. Use a Borel linear ordering to select from
each connected component $C$ of $B^{\prime}$ a point $x_{C}$ that belongs to a
non-digon block of cardinality $2$, and collect these points $x_{C}$ into a
set $B^{\prime\prime}$. Then use Theorem 4.2 to produce a Borel $L$-dicoloring
$a$ of $D[B_{0}\setminus B^{\prime\prime}]$. To color the points of
$B^{\prime\prime}$, note that, if $x\in B^{\prime\prime}$, then there is some
neighbor $y$ of $x$ such that $\\{x,y\\}$ is a maximal biconnected set that is
not a digon. In particular, no dicycle contains both $x$ and $y$. So, if
$L(x)$ contains $a(y)$, then $a$ may be extended to $x$ by setting
$a(x)=a(y)$. Otherwise, there is some color in $L(x)$ which does not appear
among both the out-neighbors and the in-neighbors of $x$, and so again $a$ can
be extended to $x$ by setting $a(x)$ to be the least such color. ∎

Now we have nearly all the tools required to prove Theorem 1.6. We next need a
result of [CMT16] which shows that, modulo a null set or a meager set, an
undirected acyclic graph in which no connected component has $0$ or $2$ ends
admits a one-ended Borel function. Recall that, if $G$ is a locally finite
graph on a set $X$, then a set $B\subseteq X$ is $G$-invariant if, whenever
$x\in B$ and there is a path from $x$ to $y$ through $G$, then $y\in B$. If
$D$ is a digraph on $X$, then we say $B\subseteq X$ is $D$-invariant if $B$ is
$\tilde{D}$-invariant. A ray in $G$ is an infinite sequence
$(x_{n})_{n\in\mathbb{N}}$ of pairwise-adjacent vertices in $G$ such that
$x_{n}\neq x_{m}$ whenever $n\neq m$. Two rays $r_{0},r_{1}$ in $G$ are end-
equivalent if, whenever $S\subseteq X$ is finite, $r_{0}$ and $r_{1}$
eventually lie in the same connected component of $G[X\setminus S]$. End-
equivalence is an equivalence relation on the set of rays; the equivalence
classes are called ends.

######  Theorem 4.11 ([CMT16], Theorem 1.5).

Let $G$ be a locally finite acyclic graph on a standard Borel space $X$.
Assume no connected component of $G$ has either $0$ or $2$ ends.

  1. (1)

For any Borel probability measure $\mu$ on $X$, there are a $\mu$-conull,
$G$-invariant Borel set $B$ and a one-ended Borel function $f:B\rightarrow X$
whose graph is contained in $G$.

  2. (2)

For any Polish topology $\tau$ compatible with the Borel structure on $X$,
there are a $\tau$-comeager, $G$-invariant Borel set $B$ and a one-ended Borel
function $f:B\rightarrow X$ whose graph is contained in $G$.

Next, we show that any bounded-degree Borel digraph $D$ having no connected
components which are $0$-ended or $2$-ended Gallai trees is Borel degree-list-
dicolorable modulo a small set. For the proof, we apply 4.11 to an acyclic
sub-digraph $D^{\prime}$ of $D$. The digraph $D^{\prime}$ is constructed by
removing edges from the blocks of $\tilde{D}$. Each such block induces either
a cycle or a complete graph; from each complete graph, edges are removed until
only a maximal-length cycle remains, and then from each cycle, the least
(according to some Borel linear ordering on the set of edges) edge is removed.

######  Theorem 4.12.

Let $D$ be a Borel digraph of bounded degree on a standard Borel space $X$.
Assume that $D$ has no finite connected components that are Gallai trees and
no infinite connected components that are $2$-ended Gallai trees. Then:

  1. (1)

For any Borel probability measure $\mu$ on $X$, there is a $\mu$-conull,
$D$-invariant Borel set $B$ such that $D[B]$ is Borel degree-list-dicolorable.

  2. (2)

For any Polish topology $\tau$ compatible with the Borel structure on $X$,
there is a $\tau$-comeager, $D$-invariant Borel set $B$ such that $D[B]$ is
Borel degree-list-dicolorable.

###### Proof.

We prove (1); the proof of (2) proceeds in the same way.

Let $L$ be a list assignment such that $|L(x)|\geq d^{\max}(x)$ for all $x\in
X$. By the assumptions in the theorem statement together with Theorem 4.10, we
may assume without loss of generality that each connected component of $D$ is
an infinite Gallai tree that does not have $2$ ends. Then each block in $D$
induces a finite dicycle, a finite odd symmetric cycle, or a finite complete
symmetric digraph. So, in the underlying graph $\tilde{D}$, each block induces
either a cyclic graph or a complete graph.

Now let $E$ denote the set of edges of $\tilde{D}$. Note that each element of
$E$ is contained in a unique block. We now create a subset
$E^{\prime}\subseteq E$ as follows. Let $<_{X}$ be a Borel linear ordering of
$X$, and let $<_{E}$ be a Borel linear ordering of $E$. From each block of
$\tilde{D}$ that induces a cyclic graph, remove the $<_{E}$-least edge; from
each block $M$ of $\tilde{D}$ that induces a complete graph of cardinality at
least $3$, write $M=\\{x_{0},x_{1},\dots,x_{k}\\}$ in ascending order
according to $<_{X}$, and then delete all edges of $M$ except
$\\{x_{0},x_{1}\\},\\{x_{1},x_{2}\\},\dots,\\{x_{k},x_{0}\\}$ before also
deleting the $<_{E}$-least edge in the list
$\\{x_{0},x_{1}\\},\\{x_{1},x_{2}\\},\dots,\\{x_{k},x_{0}\\}$. Now define a
sub-digraph $D^{\prime}$ of $D$ whose vertex set is $X$ and whose arc set is
$A^{\prime}$, where $(x,y)\in A^{\prime}$ if and only if $(x,y)\in A$ and
$\\{x,y\\}\in E^{\prime}$.

We prove several claims about $D^{\prime}$. Note first that, if $x,y$ are
adjacent in $D$, then there is a path from $x$ to $y$ through
$\widetilde{D^{\prime}}$; indeed, the edge between $x$ and $y$ in the
underlying graph $\tilde{D}$ determines a unique block $M$. If $M$ has
cardinality $2$, then the edge $\\{x,y\\}$ belongs to $E^{\prime}$. Otherwise,
if $\tilde{D}[M]$ is a cycle, then there is a path through $M$ from $x$ to $y$
which does not contain the edge $\\{x,y\\}$; if $\tilde{D}[M]$ is a complete
graph, then $\widetilde{D^{\prime}}[M]$ is a cycle missing just one edge, so
that again there is a path through $M$ from $x$ to $y$ which does not contain
the edge $\\{x,y\\}$. This implies that no connected component of $D^{\prime}$
is $0$-ended, since no connected component of $D$ is $0$-ended. This also
implies that, if $B\subseteq X$ is $D^{\prime}$-invariant, then $B$ is also
$D$-invariant.

Next, to see that $D^{\prime}$ is acyclic, note that any cycle $C$ in
$\tilde{D}$ induces either a cyclic graph or a complete graph. If $C$ induces
a cyclic graph, then some edge of $C$ is deleted in passing from $D$ to
$D^{\prime}$. If $C$ induces a complete graph, then let $M$ be the maximal
complete graph containing $C$. Then at least one of the edges of $M$ that is
removed in passing to $D^{\prime}$ is an edge of $C$.

Finally, to see that no connected component of $D^{\prime}$ is $2$-ended, note
first that the number of ends in a connected component of $D$ is less than or
equal to the number of ends in the corresponding connected component of
$D^{\prime}$. Suppose now that there are two rays $r,r^{\prime}$ in the same
connected component of $D^{\prime}$ such that, for some finite set $S\subseteq
X$, $r\setminus S$ and $r^{\prime}\setminus S$ do not eventually lie in the
same connected component of $D^{\prime}[X\setminus S]$. Let
$T=S\cup\bigcup\\{M\in[E_{D}]^{<\infty}:M\text{ is a block containing a point
of $S$}\\}$. Then it is easy to prove that $r\setminus T$ and
$r^{\prime}\setminus T$ do not eventually lie in the same connected component
of $D[X\setminus T]$. So, since no connected component of $D$ is $2$-ended, no
connected component of $D^{\prime}$ is $2$-ended.

It now follows from Theorem 4.11 that there are a $\mu$-conull,
$D^{\prime}$-invariant Borel set $B$ and a one-ended Borel function
$f:B\rightarrow X$ whose graph is contained in $\tilde{D^{\prime}}$. Note that
$B$ is $D$-invariant by the claim above and that the graph of $f$ is contained
in $\tilde{D}$. By Theorem 4.2, $D[B]$ has a Borel $L$-dicoloring. ∎

Finally, we prove Theorem 1.6. We restate the theorem here for convenience.

######  Theorem 4.13.

Let $D$ be a Borel digraph on a standard Borel space $X$. Suppose there is
$d\geq 3$ such that $d^{\max}(x)\leq d$ for all $x\in X$, and assume $D$ does
not contain the complete symmetric digraph on $d+1$ vertices. Then:

  1. (1)

For any Borel probability measure $\mu$ on $X$, there is a $\mu$-measurable
$d$-dicoloring of $D$.

  2. (2)

For any Polish topology $\tau$ compatible with the Borel structure on $X$,
there is a $\tau$-Baire-measurable $d$-dicoloring of $D$.

###### Proof.

By Corollary 4.5, we may assume that $d^{\max}(x)=d^{\min}(x)=d$ for all $x\in
X$. Note that, if all the vertices in a finite Gallai tree have out-degree and
in-degree equal to $d$, then the Gallai tree is the complete symmetric digraph
on $d$ vertices. Also, if all the vertices in an infinite $2$-ended Gallai
tree have out-degree and in-degree equal to $d$, then either $d=1$ and the
tree is a one-directional bi-infinite line, or $d=2$ and the tree is a
symmetric bi-infinite line. Since $d\geq 3$, it follows from Theorem 4.12 that
$D$ has a ($\mu$\- or $\tau$-)measurable $d$-dicoloring. ∎

##  5\. Future Directions

Here we outline two potential future research projects.

Connections among digraph combinatorics, LOCAL algorithms, and the Lovász
local lemma. Bernshteyn’s seminal paper [Ber23] reveals a deep connection
between descriptive graph combinatorics and LOCAL coloring algorithms, which
are efficient distributed algorithms for graph coloring. In particular,
deterministic LOCAL coloring algorithms can be used to produce Borel colorings
([Ber23], Theorem 2.10), and randomized LOCAL coloring algorithms can be used
to produce ($\mu$\- or Baire-)measurable colorings ([Ber23], Theorem 2.14).

The main tool in the proof of the latter result is a measurable version of the
symmetric Lovász local lemma. Let $p<1$, and consider a set $\mathcal{S}$ of
events, each of which has probability at most $p$. Suppose that each event in
$\mathcal{S}$ depends on only a small number $d$ of other events in
$\mathcal{S}$. If $p$ and $d$ satisfy a certain relationship, then the local
lemma ensures that the probability that none of the events in $\mathcal{S}$
occurs is nonzero. For graph coloring, we may take $\mathcal{S}$ to be the set
of events in which some vertex shares a color with one of its neighbors; for a
graph of bounded degree, each such event has probability bounded away from
$1$. Furthermore, due to the local nature of proper colorings, each event in
$\mathcal{S}$ depends on only a small number of other events in $\mathcal{S}$.
Bernshteyn’s measurable symmetric local lemma then ensures the existence of a
measurable coloring in which adjacent vertices do not share colors.

We would like to explore whether there is a digraph version of Bernshteyn’s
result that efficient randomized LOCAL algorithms yield measurable graph
colorings. One strategy would be to attempt to apply the measurable symmetric
local lemma. However, unlike the problem of producing a proper coloring, the
problem of producing a dicoloring is not a local problem; directed cycles can
be arbitrarily long. So, we ask the following question.

######  Question 5.1.

Are there efficient algorithms suitable for producing Borel or measurable
dicolorings?

While the symmetric local lemma cannot be directly applied to obtain
dicolorings, there are other versions of the local lemma that may be of use.
For instance, generalizations of the Lovász local lemma which appear in the
book of Alon and Spencer ([AS08]) and which were further developed by Kun
([BFK22]) allow for dependencies of events in $\mathcal{S}$ on arbitrarily
many other elements of $\mathcal{S}$ under certain additional constraints.
Bernshteyn provides an overview of these results in Section 1.2 of [Ber19].
The generalized versions of the Lovász local lemma have been important in
proving combinatorial results about undirected graphs, including the classical
theorem of Johansson ([Joh96]) which improves the Brooks’s theorem upper bound
on chromatic numbers of triangle-free undirected graphs.

######  Question 5.2.

Is there an analogue of Johansson’s theorem for directed graphs?

Applications to hypergraph colorings. A hypergraph $\mathcal{H}$ consists of a
set $X$ of vertices and a set $\mathcal{E}\subseteq\mathcal{P}(X)$ of
hyperedges. A (proper) vertex coloring of $\mathcal{H}$ is a function $c$ on
the set $X$ of vertices of $\mathcal{H}$ such that, for any hyperedge
$E\in\mathcal{E}$, there are $x,y\in E$ such that $c(x)\neq c(y)$.

The study of descriptive hypergraph combinatorics is currently in its infancy.
However, note that, for any directed graph $D$ on a set $X$, producing a
dicoloring of $D$ is equivalent to producing a vertex coloring of the
hypergraph on $X$ whose hyperedges are the directed cycles of $D$. As a
result, it may be instructive to apply the techniques of descriptive
dicoloring to obtain new results on descriptive hypergraph coloring.

One open problem to which descriptive hypergraph combinatorics may be
applicable is the following, which originated with work of Day and Marks
([DM20]).

######  Question 5.3.

Let
$\Gamma=(\mathbb{Z}/2\mathbb{Z})^{*3}=\langle\alpha,\beta,\gamma\mathrel{|}\alpha^{2}=\beta^{2}=\gamma^{2}=1\rangle$,
and let $a:\Gamma\curvearrowright 2^{\Gamma}$ be the action of $\Gamma$ on
$2^{\Gamma}$ by left shift. Put $X=\text{Free}(2^{\Gamma})$, and let

$\displaystyle A$
$\displaystyle=\\{\dots,\beta^{-1}\alpha^{-1},\alpha^{-1},1,\beta,\alpha\beta,\dots\\},$
$\displaystyle B$
$\displaystyle=\\{\dots,\gamma^{-1}\beta^{-1},\beta^{-1},1,\gamma,\beta\gamma,\dots\\},$
$\displaystyle C$
$\displaystyle=\\{\dots,\alpha^{-1}\gamma^{-1},\gamma^{-1},1,\alpha,\gamma\alpha,\dots\\}.$

Does there exist a Borel set $S\subseteq X$ such that, for each $x\in X$, both
$S$ and $X\setminus S$ meet $A\cdot x$, $B\cdot x$, and $C\cdot x$?

In the question statement, if we take $\mathcal{H}$ to be the hypergraph whose
vertex set is $X$ and whose hyperedge set is $\mathcal{E}=\\{A\cdot x:x\in
X\\}\cup\\{B\cdot x:x\in X\\}\cup\\{C\cdot x:x\in X\\}$, then we are asking
whether $\mathcal{H}$ has a Borel vertex $2$-coloring.

The question has a positive answer when “Borel” is weakened to “measurable”.
One strategy to make the problem more amenable in the Borel context is to
include additional restrictions that result in a more “local” problem. This
may be done by adding, for some appropriately chosen $n\in\mathbb{N}$, the
relations $(\alpha\beta)^{n}=(\beta\gamma)^{n}=(\alpha\gamma)^{n}=1$ to the
group $\Gamma$. Consider then the Schreier digraph $D$ whose vertex set is
$X=\text{Free}(2^{\Gamma})$ and in which there is an arc from $x\in X$ to
$y\in X$ if $x\neq y$ and $\alpha\cdot x=y$, $\beta\cdot x=y$, or $\gamma\cdot
x=y$. If $D$ admits a Borel $2$-dicoloring, then since for each $x\in X$ the
sets $A\cdot x,B\cdot x,$ and $C\cdot x$ contain dicycles, this would give the
desired vertex coloring of the associated hypergraph.

######  Question 5.4.

In the setting of Question 5.3, is there $n\in\mathbb{N}$ such that the
addition of the relations
$(\alpha\beta)^{n}=(\beta\gamma)^{n}=(\alpha\gamma)^{n}=1$ to the group
$\Gamma$ results in a Schreier digraph with a Borel $2$-dicoloring?

## Acknowledgments

We would like to thank Andrew Marks for many helpful conversations about the
content of this paper. In particular, Marks suggested the proof of Proposition
4.1, posed Questions 5.2 and 5.4, and illuminated the connections between
dicoloring and hypergraph coloring discussed in Section 5.

## References

  * [AA22] Pierre Aboulker and Guillaume Aubian.  Four proofs of the directed Brooks’ theorem.  Discrete Mathematics, 346:1–10, 2022.
  * [AS08] Noga Alon and Joel Spencer.  The Probabilistic Method.  Springer, 3 edition, 2008.
  * [Ber19] Anton Bernshteyn.  Measurable versions of the Lovász local lemma and measurable graph colorings.  Advances in Mathematics, 353:153–223, 2019.
  * [Ber23] Anton Bernshteyn.  Distributed algorithms, the Lovász local lemma, and descriptive combinatorics.  Inventiones Mathematicae, 233:495–542, 2023.
  * [BFK22] Itai Benjamini, Mikolaj Fraczyk, and Gábor Kun.  Expander spanning subgraphs with large girth.  Israel Journal of Mathematics, 251:156–172, 2022.
  * [Bor77] Oleg Borodin.  Criterion of chromaticity of a degree prescription (in Russian).  In Abstracts of IV All-Union Conference on Theoretical Cybernetics (Novosibirsk), pages 127–128, 1977.
  * [Bro41] Rowland Brooks.  On colouring the nodes of a network.  Mathematical Proceedings of the Cambridge Philosophical Society, 37:194–197, 1941.
  * [CM16] Clinton Conley and Benjamin Miller.  A bound on measurable chromatic numbers of locally finite Borel graphs.  Mathematical Research Letters, 23:1633–1644, 2016.
  * [CMT16] Clinton Conley, Andrew Marks, and Robin Tucker-Drob.  Brooks’ theorem for measurable colorings.  Forum of Mathematics, Sigma, 4:1–23, 2016.
  * [DM20] Adam Day and Andrew Marks.  On a question of Slaman and Steel, April 2020.  https://arxiv.org/abs/2004.00174.
  * [ERT79] Paul Erdős, Arthur Rubin, and Herbert Taylor.  Choosability in graphs.  In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, volume 26, pages 125–157, 1979.
  * [HM11] Ararat Harutyunyan and Bojan Mohar.  Gallai’s theorem for list coloring of digraphs.  SIAM Journal on Discrete Mathematics, 25:170–180, 2011.
  * [Joh96] Anders Johansson.  Asymptotic choice number for triangle free graphs.  Technical Report 91-5, DIMACS, 1996.
  * [Kec95] Alexander Kechris.  Classical Descriptive Set Theory.  Springer, 1995.
  * [KST99] Alexander Kechris, Sławomir Solecki, and Stevo Todorčević.  Borel chromatic numbers.  Advances in Mathematics, 141:1–44, 1999.
  * [Mar16] Andrew Marks.  A determinacy approach to Borel combinatorics.  Journal of the American Mathematical Society, 29:579–600, 2016.
  * [Mar17] Andrew Marks.  Uniformity, universality, and computability theory.  Journal of Mathematical Logic, 17:1–50, 2017.
  * [Moh03] Bojan Mohar.  Circular colourings of edge-weighted graphs.  Journal of Graph Theory, 43:107–116, 2003.
  * [Moh10] Bojan Mohar.  Eigenvalues and colourings of digraphs.  Linear Algebra and its Applications, 432:2273–2277, 2010.
  * [NL82] Victor Neumann-Lara.  The dichromatic number of a digraph.  Journal of Combinatorial Theory, Series B, 34:265–270, 1982.
  * [RX23] Dilip Raghavan and Ming Xiao.  Borel order dimension.  https://www.computability.org/comp2023/slides/raghavan.pdf, 2023.  Accessed April 2024.
  * [Whi32a] Hassler Whitney.  Congruent graphs and the connectivity of graphs.  American Journal of Mathematics, 54:150–168, 1932.
  * [Whi32b] Hassler Whitney.  Non-separable and planar graphs.  Transactions of the American Mathematical Society, 34:339–362, 1932.