Acyclic Colorings of Directed Graphs
Noah Golowich\thanks{Research Science Institute
Massachusetts Institute of Technology
Cambridge MA.
The {acyclic chromatic number of a directed graph $D$, denoted $\chi_A(D)$, is the minimum positive integer $k$ such that there exists a decomposition of the vertices of $D$ into $k$ disjoint sets, each of which induces an acyclic subgraph. For any $m \geq 1$, we introduce a generalization of the acyclic chromatic number, namely $\chi_m(D)$, which is the minimum number of sets into which the vertices of a digraph can be partitioned so that each set is weakly $m$-degenerate. We show that for all digraphs $D$ without directed 2-cycles, $\chi_m(D) \leq \frac{4\bar{\Delta(D){4m+1 + o(\bar{\Delta(D))$. Because $\chi_1(D) = \chi_A(D)$, we obtain as a corollary that $\chi_A(D) \leq \frac{4{5 \cdot \bar{\Delta(D) + o(\bar{\Delta(D))$, significantly improving a bound of Harutyunyan and Mohar. %A related question to finding $\chi_A(D)$ is finding the maximum size of an acyclic induced subgraph of $D$. We show that every digraph on $n$ vertices with average out-degree $d$ contains an acyclic induced subgraph of size $\frac{2n{d+4$, improving a bound of Aharoni et al. %We finally improve a bound on the largest acyclic induced subgraph by Ben-Eliezer et al. for digraphs in which the total degree of each vertex is equal.
chromatic_number_max_degree4.tex
\documentclass[12pt]{article}
\usepackage{amsfonts,amssymb,amsmath,titling,titlesec,cancel,amsthm,color, graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{verbatim,tikz}
\usetikzlibrary{arrows}
\usepackage{epstopdf}
\usepackage{graphicx}
\usepackage{pifont}
\usepackage{color}
\usepackage{tkz-graph}
\usepackage{caption,subcaption}

\epstopdfDeclareGraphicsRule{.gif}{png}{.png}{convert gif:#1 png:\OutputFile}
\AppendGraphicsExtensions{.gif}



% Set style parameters
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\headsep}{0in}
\setlength{\headheight}{0in}
\setlength{\topmargin}{0in}
\setlength{\parskip}{6pt}

\setlength{\droptitle}{-0.95in}
\titleformat{\section}{\large\bfseries}{\thesection.}{1em}{}



% Definitions
\makeatletter
\newtheorem*{rep@theorem}{\rep@title}
\newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
 \def\rep@title{#2 \ref{##1}}%
 \begin{rep@theorem}}%
 {\end{rep@theorem}}}
\makeatother

\newreptheorem{theorem}{Theorem}
\newreptheorem{corollary}{Corollary}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem*{theorem*}{Theorem}
\newtheorem*{corollary*}{Corollary}

\title{Acyclic Colorings of Directed Graphs}
\author{Noah Golowich\thanks{Research Science Institute, Massachusetts Institute of Technology, Cambridge MA.}}
\date{\today}

\begin{document}
\tikzset{
    every node/.style={
        circle,
        draw,
        solid,
        fill=black!50,
        inner sep=0pt,
        minimum width=4pt
    }
}
\maketitle
\begin{abstract}

The {\it acyclic chromatic number} of a directed graph $D$, denoted $\chi_A(D)$, is the minimum positive integer $k$ such that there exists a decomposition of the vertices of $D$ into $k$ disjoint sets, each of which induces an acyclic subgraph. For any $m \geq 1$, we introduce a generalization of the acyclic chromatic number, namely $\chi_m(D)$, which is the minimum number of sets into which the vertices of a digraph can be partitioned so that each set is weakly $m$-degenerate. We show that for all digraphs $D$ without directed 2-cycles, $\chi_m(D) \leq \frac{4\bar{\Delta}(D)}{4m+1} + o(\bar{\Delta}(D))$. Because $\chi_1(D) = \chi_A(D)$, we obtain as a corollary that $\chi_A(D) \leq \frac{4}{5} \cdot \bar{\Delta}(D) + o(\bar{\Delta}(D))$, significantly improving a bound of Harutyunyan and Mohar.
%A related question to finding $\chi_A(D)$ is finding the maximum size of an acyclic induced subgraph of $D$. We show that every digraph on $n$ vertices with average out-degree $d$ contains an acyclic induced subgraph of size $\frac{2n}{d+4}$, improving a bound of Aharoni et al.
%We finally improve a bound on the largest acyclic induced subgraph by Ben-Eliezer et al. for digraphs in which the total degree of each vertex is equal.
\end{abstract}


\section{Introduction}
A proper {\it vertex coloring} of an undirected graph partitions its vertices into independent sets. To extend this notion to directed graphs (digraphs), we consider acyclic sets instead of independent sets. An {\it acyclic set} in a digraph is a set of vertices whose induced subgraph contains no directed cycle. The {\it acyclic chromatic number} of a digraph $D$, denoted $\chi_A(D)$, is then defined to be the minimum number of acyclic sets into which the vertices of $D$ can be partitioned. 


%Studying the acyclic subgraphs of digraphs has applications in scheduling and deadlock resolution. For instance, Jain et al. \cite{generalized_jain_2005} studied acyclic subgraphs to develop efficient approximation algorithms for deadlock resolution. Actions in a computer may be represented as vertices in a digraph. A directed edge is drawn from action $A$ to action $B$ if $A$ is waiting for $B$ to finish. This situation can happen for example if $B$ is holding up a processor that $A$ needs to terminate. Therefore, a directed cycle in such a digraph represents a situation where none of the events in the cycle can finish since each is waiting for the following event to be complete. This situation is called deadlock, and one way to resolve the deadlock is to study acyclic subgraphs of a digraph. Each acyclic subgraph contains no cycles, and therefore no deadlock, so obtaining bounds on the size of acyclic subgraphs can lead to improvements in efficient deadlock resolution. 




%\subsection{Preliminary definitions}

%MOVE THE BELOW SOMEWHERE
%Given a directed graph $D$, we let $V(D)$ denote the set of vertices of $D$, and $E(D)$ denote the set of edges of $D$. For any vertex $v$ in a directed graph, the {\it out-neighborhood} $N^+(v)$ of $v$ is the set of all vertices $u$ for which $vu$ is an edge, and the {\it in-neighborhood} $N^-(v)$ of $v$ is the set of all vertices $u$ for which $uv$ is an edge. The {\it out-degree} of $v$ is $d^+(v) = |N^+(v)|$, and the {\it in-degree} of $v$ is $d^-(v) = |N^-(v)|$.
%The {\it digirth} of a directed graph is the length of its shortest directed cycle. All logarithms in this paper are taken base 2.

Many upper bounds on the chromatic number of undirected graphs are phrased in terms of $\Delta(G)$, the maximum degree of $G$.
To extend this notion to directed graphs, there are a few options which measure the maximum degree. Given a digraph $D$, $\widetilde{\Delta}(D)$ is the maximum geometric mean of the in-degree and the out-degree of a vertex in $D$, and $\bar{\Delta}(D)$ is the maximum arithmetic mean of the in-degree and the out-degree of a vertex in $D$. Notice that if the out-degrees and in-degrees of all vertices in $D$ are equal, then $ \widetilde{\Delta}(D) = \bar{\Delta}(D)$.

The acyclic chromatic number $\chi_A(D)$ is one of many chromatic numbers which have been defined for digraphs. Bokal et al.~\cite{circular_bokal_2004} introduced the circular chromatic number of a digraph $D$, denoted $\chi_c(D)$, as a generalization of the acyclic chromatic number. Let $S_p$ denote the circle with perimeter $p$, and for $x, y \in S_p$, let $d(x, y)$ denote the clockwise distance from $x$ to $y$. Then the circular chromatic number $\chi_c(D)$ is the infimum of all positive real numbers $p$ for which there exists a function $c: V(D) \rightarrow S_p$ such that for each edge $uv$ of $D$, $d(c(u), c(v)) \geq 1.$ Bokal et al.~showed that $\chi_c(D)$ takes on rational values, and moreover, that $\chi_A(D) - 1 < \chi_c(D) \leq \chi_A(D)$. Chen et al.~\cite{chen_coloring_2014} have also considered defining a digraph coloring simply as a coloring of the underlying undirected graph, and proved bounds on this chromatic number in terms of the lengths modulo $k$ of directed cycles of the digraph.

In this paper, we use the following generalization of the acyclic chromatic number and deduce new bounds on the acyclic chromatic number itself as a special case of our results. For a positive integer $m$, a digraph $D$ is said to be {\it weakly $m$-degenerate} if for every induced subgraph of $D$, there is a vertex of out-degree or in-degree strictly less than $m$. Therefore, a digraph is weakly 1-degenerate if and only if it is acyclic. Given a positive integer $k$, a {\it $(k, m)$-degenerate coloring} of $D$ is a partition of $V(D)$ into $k$ sets, each of which is weakly $m$-degenerate. Given a positive integer $m$, we denote $\chi_m(D)$, the {\it $m$-degenerate chromatic number} of $D$, as the smallest positive integer $k$ such that $D$ has a $(k, m)$-degenerate coloring. Notice that $\chi_1(D) = \chi_A(D)$; hence the parameter $\chi_m(D)$ is a generalization of $\chi_A(D)$. Bokal et al.~\cite{circular_bokal_2004} showed some further connections between weak degeneracy and acyclic colorings. For instance, if a digraph is weakly $m$-degenerate, then $\chi_A(D) \leq m+1$; moreover, this bound is tight for each positive integer $m$.

%\subsection{Chromatic number from maximal degree}
The acyclic chromatic number has received the most attention among digraph chromatic numbers because recent results \cite{acyclic_aharoni_2008, circular_bokal_2004, digraph_keevash_2013, two_harut_2012, ben_size_2012} suggest that the acyclic chromatic number in digraphs behaves similarly to the chromatic number in undirected graphs. 
%Moreover,  a related question to finding the acyclic chromatic number, finding the size of the largest acyclic set in a digraph, has applications in scheduling and deadlock resolution \cite{generalized_jain_2005}. 
Much still remains to be learned however. For instance, it is easily proved using the greedy algorithm that $\chi_A(D) \leq \bar{\Delta}(D) + 1$; this is analogous to the fact that in an undirected graph $G$, $\chi(G) \leq \Delta(G) + 1$. However, this bound is not tight for most digraphs.

In the case of undirected graphs, Brooks \cite{brooks_coloring_1941} made the first improvement on the obvious bound of $\chi(G) \leq \Delta(G) + 1$; he showed that $\chi(G) \leq \Delta(G)$ unless $G$ is a complete graph or an odd cycle. Borodin and Kostochka \cite{borodin_upper_1977} and Catlin \cite{catlin_bound_1978} then independently strengthened Brooks' theorem, showing that if $G$ is $K_4$-free, then $\chi(G) \leq \left\lceil\frac{3(\Delta(G) + 1)}{4}\right\rceil$. Mohar \cite{mohar_eigen_2009} recently proved an analogue of Brooks' theorem for digraphs such that at most one edge connects any pair of vertices; such a digraph is called an {\it oriented graph}. It follows from Mohar's results that if $D$ is an oriented graph, then $\chi_A(D) \leq \lceil\bar{\Delta}(D)\rceil$ unless $D$ is a directed cycle.
However, it appears that this upper bound on $\chi_A(D)$ can be significantly improved further; Harutyunyan and Mohar \cite{two_harut_2012} credit McDiarmid and Mohar with the following conjecture.
\begin{conjecture}[McDiarmid \& Mohar, 2002 \cite{two_harut_2012}]
\label{conj:everything}
Every oriented graph $D$ satisfies {$\chi_A(D) = O\left(\frac{\bar{\Delta}(D)}{\log \bar{\Delta}(D)}\right)$}.
\end{conjecture}
Conjecture \ref{conj:everything} is analogous to a result for undirected graphs by Kim \cite{kim_brooks_1995}, who showed that \mbox{$\chi(G) \leq (1 + o(1)) \frac{\Delta(G)}{\log \Delta(G)}$} if the girth (length of the shortest cycle) of $G$ is greater than 4. Johansson \cite{johannson_asymptotic} later extended Kim's bound to graphs $G$ of girth greater than 3, and Jamall \cite{jamall_brooks_2011} has since used a simpler proof to strengthen Johansson's bound by a constant factor. Kim, Johansson, and Jamall all used the {\it pseudo-random method} to prove upper bounds on the chromatic number. The central idea of this method is that given a graph $G$, and the goal of using $\Delta(G)/k$ colors, where $k$ is a positive integer, the algorithm goes through several rounds and assigns colors randomly to a subset of the uncolored vertices at each round. Eventually a proper coloring of all the vertices of $G$ will be found with positive probability.

Harutyunyan and Mohar \cite{strengthened_harut_2011} applied the pseudo-random method to digraphs to show that $\chi_A(D) \leq (1 - e^{-13})\widetilde{\Delta}(D)$, which only slightly improves upon the trivial bound of $\chi_A(D) \leq \bar{\Delta}(D) + 1$ and is far from the bound given in Conjecture \ref{conj:everything}. Therefore, Harutyunyan and Mohar \cite{strengthened_harut_2011} posed the following relaxation of Conjecture \ref{conj:everything}. %The following conjecture is paraphrased from \cite{strengthened_harut_2011}.
\begin{conjecture}[Harutyunyan \& Mohar, 2011 \cite{strengthened_harut_2011}]
\label{conj:harutdelta}
Let $D$ be an oriented graph. Then $\chi_A(D) \leq \left\lceil \frac{\widetilde{\Delta}(D)}{2} \right\rceil + 1.$
\end{conjecture}
In Theorem \ref{thm:fracdelta}, we prove an upper bound on the $m$-degenerate chromatic number of any digraph $D$ in terms of $\bar{\Delta}(D)$. It is a special case of Theorem \ref{thm:fracdelta} that  we can significantly improve Harutyunyan and Mohar's bound, thus making progress towards Conjecture \ref{conj:harutdelta}. %to \mbox{$\chi_A(D) \leq \frac{4}{5}\cdot\bar{\Delta}(D) + o(\bar{\Delta}(D))$}
%We begin by introducing some notation and definitions that will be useful in this section. 
%The generalization of the acyclic chromatic number that we consider in Theorem \ref{thm:fracdelta} relies on the notion of degeneracy.
%A {\it strongly connected component} of a digraph $D$ is an induced subgraph $H$ such that for any $u, v \in H$, there are directed paths from $u$ to $v$ and from $v$ to $u$.
%Theorem \ref{thm:fracdelta} gives an upper bound on $\chi_m(D)$ in terms of $\bar{\Delta}(D)$.


\begin{theorem}
\label{thm:fracdelta}
Let $m$ be a positive integer. Suppose we are given an oriented graph $D$ with $\bar{\Delta}(D) \geq 2m$. Then
\begin{equation}
\chi_m(D)  \leq \left\lfloor \frac{\bar{\Delta}(D)  -\left(\frac{1}{2} \right)  \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{2m + 1/2} \right\rfloor}{m}\right\rfloor + 1\nonumber.
\end{equation}
\end{theorem}

By taking $m = 1$, the following corollary follows immediately from Theorem \ref{thm:fracdelta}.

\begin{corollary}
\label{cor:acyclic}
For an oriented graph $D$ with $\bar{\Delta}(D) \geq 2$,  $\chi_A(D) \leq \left\lfloor \frac{4}{5}\cdot\bar{\Delta}(D) + \frac{2}{5} \right\rfloor + 1.$
\end{corollary}

We prove Theorem \ref{thm:fracdelta} by using a strategy similar to one originally introduced by Borodin and Kostochka \cite{borodin_acyclic_1979} and by Catlin \cite{catlin_bound_1978} to prove an upper bound on the chromatic number in undirected graphs. Specifically, we show that the vertices of a directed graph $D$ can be partitioned into several subsets, each inducing a subgraph $D_i \subset D$, such that $\bar{\Delta}(D_i)$ is small. We then use this to show that $\chi_m(D_i)$ is also small, meaning that we can find an upper bound on \mbox{$\chi_m(D) \leq \sum_{i} \chi_m(D_i)$}.
%\subsection{Large acyclic subgraphs}


%A quantity related to the acyclic chromatic number of a digraph $D$ is the size of a largest acyclic set of vertices in $D$, which is denoted by $\alpha_A(D)$. Given a digraph $D$ with $n$ vertices, the values $\chi_A(D)$ and $\alpha_A(D)$ are related by the inequality $\alpha_A(D) \geq n/\chi_A(D)$, so finding an upper bound on $\chi_A(D)$ in turn gives a lower bound on $\alpha_A(D)$. Therefore, a stepping stone to finding an upper bound on the acyclic chromatic number as proposed in Conjectures \ref{conj:everything} and \ref{conj:harutdelta} is to find a lower bound on the size of the largest acyclic set.
%
%
%Aharoni et al. \cite{acyclic_aharoni_2008} showed that for any digraph $D$ with $n$ vertices and $m$ edges,
%\begin{equation}
%\label{eq:alphaa}
%\alpha_A(D) \geq \frac{n^2}{m + n}.
%\end{equation}
%
% In Theorem \ref{thm:lowdeg} below, we improve the bound in $(\ref{eq:alphaa})$ by a constant factor of 2 for general digraphs $D$.
%
%\begin{theorem}
%\label{thm:lowdeg}
%If $D$ is a digraph on $n$ vertices and $m$ edges, then $\alpha_A(D) \geq \frac{2n^2}{m+4n}$. %Then there exists an acyclic set of size $\frac{A\log_2{n\epsilon}}{\epsilon}$. That is, $\alpha_A(D) \geq \frac{A\log_2{n\epsilon}}{\epsilon}$.
%\end{theorem}
%
%
%
%We prove Theorem \ref{thm:lowdeg} using a recursive technique. At each step of the recursion, we add a vertex $v$ to the acyclic set of vertices and thereafter only consider the vertices which are not in-neighbors of $v$.
%
%Notice that when $m = O(n^2)$, the bound in $(\ref{eq:alphaa})$ shows that there is an acyclic set of only constant size, and it is natural to see if we can improve this.
%Ben-Eliezer et al. \cite{ben_size_2012} observed that if $D$ has $n$ vertices, then $\alpha_A(D) \geq \log n$. 
%Notice that when  $m \geq n^2/\log n$, the bound in $(\ref{eq:alphaa})$ is weaker than $\alpha_A(D) \geq \log n$.
%In fact, Aharoni et al. \cite{acyclic_aharoni_2008} conjectured the following stronger bound, which would be best possible, if true.
%\begin{conjecture}[\cite{acyclic_aharoni_2008}]
%\label{conj:aha}
%If $D$ is a digraph with $n$ vertices and $m$ edges, then
%\begin{equation}
%\alpha_A(D) \geq (1 + o(1))\frac{n^2}{m}\log\frac{m}{n}\nonumber.
%\end{equation}
%\end{conjecture}
%Conjecture \ref{conj:aha} remains open, even up to a constant factor, but Ben-Eliezer et al. \cite{ben_size_2012} recently proved  that
%\begin{equation}
%\label{eq:improvement}
%\alpha_A(D) \geq \frac{1}{10}\cdot \frac{n^2}{m}\cdot \frac{\log{n}}{\log{(n^2/m})}.
%\end{equation}
%Ben-Eliezer et al. \cite{ben_size_2012} then used the bound in $(\ref{eq:improvement})$ to find a lower bound on the size Ramsey number of a directed path. A proof of Conjecture \ref{conj:aha} would lead to improved lower bounds on this size Ramsey number. In Theorem \ref{thm:10better} below, we give an improvement on the bound for $\alpha_A(D)$  in  $(\ref{eq:improvement})$ by a factor of nearly 10 for a certain class of digraphs which we call {\it weakly regular digraphs}. We define a digraph to be {\it weakly regular} if the sums of the out-degree and in-degree of each vertex are all equal. %In Theorem \ref{thm:10better}, restated below, we improve the bound in ($\ref{eq:improvement}$) of Ben-Eliezer et al. by a factor of nearly 10 for weakly regular graphs.
%\begin{theorem}
%\label{thm:10better}
%Suppose $D$ is a weakly regular digraph with $n$ vertices and at most $m$ edges, and $m \geq n$. Then $D$ contains an acyclic set of size $\frac{An^2 \log{n}}{m \log{n^2/m}}$, where $A$ is any constant strictly less than 1.
%\end{theorem}
%
%The proof of Theorem \ref{thm:10better} is a refinement of the original proof of Ben-Eliezer et al. \cite{ben_size_2012}.

The organization of this paper is as follows. In Section \ref{sec:colorings}, we prove Theorem \ref{thm:fracdelta}, giving an upper bound on $\chi_m(D)$ for any digraph $D$ in terms of $\bar{\Delta}(D)$. In Section \ref{sec:betbounds}, we improve upon this bound for $m= 1$ for a particular class of digraphs. We give some concluding remarks in the final section.


\section{Acyclic colorings}
\label{sec:colorings}
Recall that Harutyunyan and Mohar \cite{strengthened_harut_2011} proved that given a digraph $D$, if $\widetilde{\Delta}(D)$ is large enough, then $\chi_A(D) \leq (1 - e^{-13})\widetilde{\Delta}(D)$. They used a non-constructive method to do so, and posed the problem of improving this bound, remarking that a different technique may be necessary. In this section, we use a constructive technique to prove Theorem \ref{thm:fracdelta}, a specific case of which (Corollary \ref{cor:acyclic}) is the significantly stronger upper bound of $\chi_A(D) \leq \frac{4}{5} \cdot \bar{\Delta}(D) + o(\bar{\Delta}(D))$. %Our bound makes significant progress towards Conjecture \ref{conj:harutdelta}. 
The outline of our proof of Theorem \ref{thm:fracdelta} is somewhat similar to that of an undirected analogue proved independently by Borodin and Kostochka \cite{borodin_upper_1977} and Catlin \cite{catlin_bound_1978}.


It is easy to show that $\chi_m(D) \leq \left\lfloor \frac{\bar{\Delta}(D)}{m}\right \rfloor + 1$; the proof is similar to that of the fact that \mbox{$\chi_A(D) \leq \lfloor\bar{\Delta}(D)\rfloor + 1$}. In particular, we color the vertices of $D$ greedily, in any order. At each step, the next vertex $v$ to be colored has either out-degree or in-degree at most $\bar{\Delta}(D)$, suppose without loss of generality out-degree. Therefore, there are at most $\left \lfloor \frac{\bar{\Delta}(D)}{m} \right \rfloor$ colors which are represented in at least $m$ out-neighbors of $v$. We now color $v$ using one of the remaining colors which is represented in less than $m$ out-neighbors of $v$. The resulting coloring is indeed $m$-degenerate, since in any subset of any color class, the vertex in that subset colored last must have less than $m$ in-neighbors or out-neighbors in that subset.


Note that Theorem \ref{thm:fracdelta} gives a significant improvement to $\chi_m(D) \leq \left\lfloor \frac{\bar{\Delta}(D)}{m}\right \rfloor + 1$ for any oriented graph $D$.
%\begin{reptheorem}{thm:fracdelta}
%Let $m$ be a positive integer. Suppose we are given an oriented graph $D$ with $\bar{\Delta}(D) \geq 2m$. Then
%\begin{equation}
%\chi_m(D)  \leq \left\lfloor \frac{\bar{\Delta}(D)  -\left(\frac{1}{2} \right)  \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{2m + 1/2} \right\rfloor}{m}\right\rfloor + 1\nonumber.
%\end{equation}
%\end{reptheorem}
%Since $\chi_1(D) = \chi_A(D)$, Corollary \ref{cor:acyclic}, restated below, follows immediately from Theorem \ref{thm:fracdelta}.
%%Of particular interest is the case where $m = 1$, where we have $\chi_m(D) = \chi_A(D)$, and partitioning $D$ into $m$-degenerate sets is equivalent to partitioning $D$ into acyclic sets. Theorem $\ref{thm:fracdelta}$ immediately implies the following Corollary \ref{cor:acyclic}:
%\begin{repcorollary}{cor:acyclic}
%%\label{cor:acyclic}
%For an oriented graph $D$ with $\bar{\Delta}(D) \geq 2$,
%\begin{equation}
%\label{eq:45ths}
%\chi_A(D) \leq \left\lfloor \frac{4}{5}\cdot\bar{\Delta}(D) + \frac{2}{5} \right\rfloor + 1.
%\end{equation}
%\end{repcorollary}
%The bound in $(\ref{eq:45ths})$ approaches $\frac{4}{5} \cdot \bar{\Delta}(D)$ as $\bar{\Delta}(D)$ approaches $\infty$. This bound is a significant improvement over the bound of $\chi_A(D) \leq (1 - e^{-13})\cdot \tilde{\Delta}(D)$ proved by Harutyunyan and Mohar.
To prove Theorem \ref{thm:fracdelta}, we begin by generalizing a directed graph analogue of Brooks' theorem \cite{brooks_coloring_1941} due to Mohar \cite{mohar_eigen_2009} to the framework of $m$-degenerate colorings. Our proofs follow similar outlines to those of Mohar.

 %Lemma \ref{lem:strong} below shows that we only have to consider the strongly connected components of a digraph when finding bounds on the acyclic chromatic number.

%We define a digraph $D$ to be {\it weakly $m$-degenerate} if for every induced subgraph of $D$, there is a vertex of out-degree or in-degree strictly less than $m$. Therefore, a digraph is weakly 1-degenerate if and only if it is acyclic. A {\it $(k, m)$-degenerate coloring} of $D$ is a partition of $V(D)$ into $k$ sets, each of which is weakly $m$-degenerate. We denote the smallest $k$ such that $D$ has a $(k, m)$-degenerate coloring by $\chi_m(D)$. Given $D$, a {\it critical vertex} is a vertex $v \in V(D)$ such that $\chi_m(D - v) < \chi_m(D)$. If every vertex of $D$ is critical and $\chi_m(D) = k$, then we define $D$ to be a {\it $(k, m)$-critical digraph}.

%\begin{lemma}
%\label{lem:inout}
%If a digraph $D$ is weakly $m$-degenerate, then in any subgraph of $D$ there exist two vertices, each of in-%degree or out-degree less than $m$.
%\end{lemma}
%\begin{proof}
%We construct a linear order of the vertices of $D$, as follows. We maintain indices $i$ and $j$, and set $i = 1$, $j = n$ initially. In the first step, we find a vertex $v \in D$ whose in-degree or out-degree is less than $m$. If $d^-(v) < m$, then we set $u_1 = v$ and increment $i$ by 1, and if $d^+(v) < m$, we set $u_n = v$ and decrement $j$ by 1.[incomplete -- just have to show this for the original digraph $D$]
%\end{proof}

%\begin{lemma}\label{lem:strong}
%Let $D_1, \ldots, D_h$ be the strongly connected components of a digraph $D$. Then $\chi_A(D) = \max\{\chi_A(D_i) : 1 \leq i \leq h\}$.
%\end{lemma}
%\begin{proof}
%Every cycle of $D$ must be entirely contained within one of the $D_i$, so we let $c = \max\{\chi(D_i)\}$, and color $D$ with $c$ colors by forming an acyclic c-coloring of each $D_i$ with colors $\{1, \ldots, c\}$. Then any monochromatic cycle must be entirely contained within some $D_i$, which is a contradiction.
%Since every cycle of $D$ must be entirely contained within one of the $D_i$, we may assume without loss of generality that the $D_i$ are ordered so that if there is an edge from $D_i$ to $D_j$ with $i \neq j$, then $i < j$.
%
%Let $c = \max\{\chi_m(D_i)\}$, and color $D$ with $c$ colors by forming a $(c, m)$-degenerate coloring of each of $D_1, \ldots, D_h$ with colors $\{1, 2, \ldots, c\}$. Pick any color $i$, $1 \leq i \leq c$, and let $H$ be the subgraph of $D$ induced by all vertices colored $i$. Furthermore let the sets of vertices of $H$ belonging to $D_1, \ldots, D_h$ be $H_1, \ldots, H_h$, respectively. Given a subset $H'$ of $H$, pick $i'$ so that $H'$ has a nonempty intersection with $H_{i'}$ and $i'$ is as small as possible. Thus if $u \in H' \cap H_j$ and $j \neq i'$, then either $u$ and $i'$ are non-adjacent or there is an edge from $i'$ to $u$. Since $H_{i'}$ is $m$-degenerate, by Lemma \ref{lem:inout}, $H'$ contains a vertex $v$ so that the in-degree of $v$ in $H_i$ is strictly less than $m$. This means that the in-degree of $v$ in $H'$ is strictly less than $m$.
%\end{proof}

%Given $D$, a {\it critical vertex} is a vertex $v \in V(D)$ such that $\chi_A(D - v) < \chi_A(D)$. If every vertex of $D$ is critical and $\chi_A(D) = k$, then we define $D$ to be a {\it $k$-critical digraph}. 

A few definitions are needed to state Lemma \ref{lem:critvertex}. Given a digraph $D$ and $u \in V(D)$, we denote the subgraph induced on $V(D)\backslash \{u\}$ by $D - u$. 
Moreover, given a positive integer $m$, a {\it critical} vertex is a vertex $v \in V(D)$ such that $\chi_m(D - v) < \chi_m(D)$. If every vertex of $D$ is critical and $\chi_m(D) = k$, then we define $D$ to be a {\it $(k, m)$-critical} digraph. %Moreover, if $u, v \in V(D)$, and $uv$ is not an edge of $D$, we denote the digraph $D'$ obtained by adding edge $uv$ to $D$ as $D' = D + uv$.
Lemma \ref{lem:critvertex} shows that critical vertices in a digraph must have large in-degree and out-degree.

\begin{lemma}
\label{lem:critvertex}
Suppose $v$ is a critical vertex in a digraph $D$, $m \geq 1$, and $\chi_m(D) = k$. Then $d^+(v), d^-(v) \geq (k-1)m$.
\end{lemma}

\begin{proof}
Suppose for the purpose of contradiction that $d^+(v) < (k-1)m$. We will show that we can find a $(k-1, m)$-degenerate coloring of $D$, a contradiction to the fact that $\chi_m(D) = k$. Since $v$ is $(k, m)$-critical, we can find a $(k-1, m)$-degenerate coloring of $D - v$.  At least one color class $c$ must be represented in less than $m$ out-neighbors of $v$ because otherwise $v$ would have at least $(k-1)m$ out-neighbors. Now we color $v$ color $c$, and claim that the subgraph $H$ induced by all vertices of color $c$ is $m$-degenerate. To see this, let $H'$ be an induced subgraph of $H$. If $v \in V(H')$, then notice that $v$ has at most $m-1$ out-neighbors in $H'$. Otherwise, note that $H'$ is a subset of a color class in a $(k-1, m)$-degenerate coloring of $D - v$, meaning that there is some vertex in $H'$ of in-degree or out-degree less than $m$. 

A similar argument shows that $d^-(v) \geq (k-1)m$.
\end{proof}



A digraph is {\it weakly connected} if the underlying undirected graph is connected. 
We next state and prove Lemma \ref{lem:trivial}, which states that we only need to consider the weakly connected components of a digraph to find its $m$-degenerate chromatic number.
\begin{lemma}
\label{lem:trivial}
If $D$ is a digraph and $D_1, \ldots, D_l$ are its weakly connected components for some positive integer $l$, then for any $m \geq 1$, $\chi_m(D) = \max_{1 \leq i \leq l} \chi_m(D_i)$.
\end{lemma}
\begin{proof}
Let $k = \max_{1 \leq i \leq l} \chi_m(D_i)$. We can find a $(k, m)$-degenerate coloring of each $D_i$, for $1 \leq i \leq l$, and the resulting composite coloring is a $(k, m)$-degenerate coloring of $D$ since there is no edge between any two weakly connected components of $D$.
\end{proof}
By Lemma \ref{lem:trivial}, a digraph $D$ which is $(k, m)$-critical is also weakly connected.




Lemma \ref{lem:2separator} shows that in a $(k,m)$-critical oriented graph, we can find a certain set of vertices, which, when removed, does not break the weakly connectedness of the oriented graph.

\begin{lemma}
\label{lem:2separator}
Suppose $m \geq 1$, $k \geq 3$, and $D$ is a $(k, m)$-critical oriented graph on $n$ vertices in which each vertex $v$ satisfies $d^+(v) = d^-(v) = (k-1)m$. Then there exists a set of vertices $u_1, u_2, \ldots, u_{m+1}, u_n \in V(D)$ such that $u_1, \ldots, u_{m+1}$ are all out-neighbors or all in-neighbors of $u_n$ and the digraph induced by $V(D) - \{u_1, \ldots, u_{m+1}\}$ is weakly connected.
\end{lemma}

\begin{proof}
Pick any $m +1$ vertices $u_1, \ldots, u_{m+1}$ which are all in-neighbors or out-neighbors of another vertex $u_n$, and let $u_{m+2}, \ldots, u_{n-1}$ be the remaining vertices of $D$. Let $D_0$ be the subgraph induced by $\{u_{m+2}, \ldots, u_n\}$. Assume that $D_0$ is not weakly connected; if it is, the proof is complete.

 Let $w$ be any vertex in $D_0$. Since $D$ is weakly connected, there is some path (not necessarily directed) from $w$ to $u_i$, for each $1 \leq i \leq m + 1$. Therefore, any weakly connected component of $D_0$ must contain a vertex which is adjacent to some $u_i$, for $1 \leq i \leq m+1$. Given a weakly connected component $C$ of $D_0$, let $s(C)$ be the set of all $u_i$ ($1 \leq i \leq m+1$) which are adjacent to some vertex of $C$, and let $N(C)$ be the subgraph of $D$ induced by $V(C) \cup s(C)$.

We now perform a multi-step process, considering many possible choices of $u_1, \ldots, u_{m+1},\\ u_n$ until we find one which forces $D_0$ to be weakly connected. If $D_0$ is not weakly connected, then choose a weakly connected component $C_1$, and suppose without loss of generality that $s(C_1) = \{u_1, \ldots, u_h\}$ for some $1 \leq h \leq m+1$. We first mark all vertices of $C_1$. Let $C_2$ be another weakly connected component of $D_0$. We next claim that there is some vertex $v \in V(C_2)$ with at least $m+1$ in-neighbors or $m+1$ out-neighbors in $V(C_2)$. To show this, we must consider two cases:

{\bf Case 1.} $m \geq 2$ or $k \geq 4$. 
Notice that each $v \in V(C_2)$ has $(k-1)m$ in-neighbors and $(k-1)m$ out-neighbors, all of which must belong to $V(N(C_2))$ by assumption. Since $m \geq 2$ and $k \geq 4$, we have that $(2k-4)m > m + 1 \geq |s(C_2)|$. Therefore, since $D$ is oriented, each $v \in V(C_2)$ must have strictly fewer than $(k-2)m$ in-neighbors or strictly fewer than $(k-2)m$ out-neighbors in $s(C_2)$. Thus $v$ has at least $m+1$ in-neighbors or $m+1$ out-neighbors in $V(C_2).$%In order for $v$ not to have $m+1$ in-neighbors or $m+1$ out-neighbors in $V(C_2)$, it must have at least $(k-2)m$ in-neighbors and $(k-2)m$ out-neighbors in $s(C_2)$. Since $D$ is oriented, we have that $(2k-4)m \leq |s(C_2)| \leq m+1$, which contradicts the fact that $m \geq 2$ or $k \geq 4$.

{\bf Case 2.} $m = 1$ and $k = 3$.
In this case, we consider acyclic colorings, and moreover, since each $v \in V(C_2)$ has 2 in-neighbors and 2 out-neighbors, our claim is true unless $|s(C_2)| = 2$ and each $v\in V(C_2)$ has 1 in-neighbor and 1 out-neighbor in $s(C_2)$. Moreover, some vertex of $s(C_2)$ must have an in-neighbor or out-neighbor which does not belong to $V(N(C_2))$; if this were not true, then $D$ would not be weakly connected. Since this vertex has a total of 4 neighbors and must be joined to each vertex of $C_2$, we have $|V(C_2)| \leq 3$. 

We first assume that $|V(C_2)| = 3$, and let $s(C_2) = \{w_1, w_2\}$. Since each vertex of $D$ has 2 in-neighbors and out-neighbors, and since $w_1$ and $w_2$ are interchangeable, $N(C_2)$ is isomorphic to the digraph shown in Figure \ref{fig:2coloring}(a). Moreover, since $D$ is $(3,1)$-critical, we can find an acyclic 2-coloring of $D - V(C_2)$.

 If $w_1$ and $w_2$ have the same color, suppose red, in this coloring, then suppose without loss of generality that there is no monochromatic directed path from $w_1$ to $w_2$ in $D - V(C_2)$. We can make this assumption because the red vertices form an induced acyclic subgraph and since $w_1$ and $w_2$ are interchangeable. 
Next, pick a vertex $x \in V(C_2)$ which has $w_1$ as its out-neighbor and $w_2$ as its in-neighbor; there exists such an $x$ since $|V(C_2)| = 3$ and at most 2 vertices in $V(C_2)$ have $w_1$ as an in-neighbor and $w_2$ as an out-neighbor. Color vertex $x$ red, and color the other 2 vertices in $V(C_2)$ the other color, suppose blue. As shown in Figure \ref{fig:2coloring}(b), this completes an acyclic 2-coloring of $D$, contradicting its $(3,1)$-criticality. 

If $w_1$ and $w_2$ have different colors in the acyclic 2-coloring of $D-V(C_2)$, then no monochromatic directed cycle in $D$ can contain a vertex in $V(C_2)$ and a vertex in $D - V(N(C_2))$. Assuming that $w_1$ is colored red and $w_2$ is colored blue, we pick 2 vertices of $V(C_2)$, which, when colored red, do not form a monochromatic directed cycle with $w_1$, and color these vertices red. We color the third vertex of $V(C_2)$ blue. As shown in Figure \ref{fig:2coloring}(c), this completes the acyclic 2-coloring of $D$ in this case also, contradicting the $(3,1)$-criticality of $D$. 

In the case that $C_2$ has 2 or fewer vertices, the proof that we can find an acyclic 2-coloring of $D$ is nearly identical.

\begin{figure}
\begin{minipage}[b]{0.3\linewidth}
\begin{center}
(a)\\
\begin{tikzpicture}

\tikzset{vertex/.style = {shape=circle,draw,minimum size=1.5em}}
\tikzset{edge/.style = {->,> = latex'}}
% vertices
\node[shape=circle,minimum size=1.5em,fill=white] (w) at  (0,0) {$w_1$};
\node[shape=circle,minimum size=1.5em,fill=white] (y) at  (0,3) {$w_2$};
\node[shape=circle,minimum size=1.5em,fill=white] (p) at  (-1.5,1.5) {};
\node[shape=circle,minimum size=1.5em,fill=white] (q) at  (-3,0) {};
\node[shape=circle,minimum size=1.5em,fill=white] (r) at  (-3,3) {};

\draw[edge] (p) to (q);
\draw[edge] (q) to (r);
\draw[edge] (r) to (p);
\draw[edge] (p) to (w);
\draw[edge] (y) to (p);
\draw[edge] (q) to [bend right](y);
\draw[edge] (w) to (q);
\draw[edge] (r) to (y);
\draw[edge] (w) to [bend right](r);
\end{tikzpicture}
\end{center}
\end{minipage}
\begin{minipage}[b]{0.3\linewidth}
\begin{center}
(b)\\
\begin{tikzpicture}

\tikzset{vertex/.style = {shape=circle,draw,minimum size=1.5em}}
\tikzset{edge/.style = {->,> = latex'}}
% vertices
\node[shape=circle,minimum size=1.5em,fill=red] (w) at  (0,0) {$w_1$};
\node[shape=circle,minimum size=1.5em,fill=red] (y) at  (0,3) {$w_2$};
\node[shape=circle,minimum size=1.5em,fill=red] (p) at  (-1.5,1.5) {$x$};
\node[shape=circle,minimum size=1.5em,fill=cyan] (q) at  (-3,0) {};
\node[shape=circle,minimum size=1.5em,fill=cyan] (r) at  (-3,3) {};

\draw[edge] (p) to (q);
\draw[edge] (q) to (r);
\draw[edge] (r) to (p);
\draw[edge] (p) to (w);
\draw[edge] (y) to (p);
\draw[edge] (q) to [bend right](y);
\draw[edge] (w) to (q);
\draw[edge] (r) to (y);
\draw[edge] (w) to [bend right](r);
\end{tikzpicture}
\end{center}
\end{minipage}
\begin{minipage}[b]{0.3\linewidth}
\begin{center}
(c)\\
\begin{tikzpicture}

\tikzset{vertex/.style = {shape=circle,draw,minimum size=1.5em}}
\tikzset{edge/.style = {->,> = latex'}}
% vertices
\node[shape=circle,minimum size=1.5em,fill=red] (w) at  (0,0) {$w_1$};
\node[shape=circle,minimum size=1.5em,fill=cyan] (y) at  (0,3) {$w_2$};
\node[shape=circle,minimum size=1.5em,fill=red] (p) at  (-1.5,1.5) {};
\node[shape=circle,minimum size=1.5em,fill=red] (q) at  (-3,0) {};
\node[shape=circle,minimum size=1.5em,fill=cyan] (r) at  (-3,3) {};

\draw[edge] (p) to (q);
\draw[edge] (q) to (r);
\draw[edge] (r) to (p);
\draw[edge] (p) to (w);
\draw[edge] (y) to (p);
\draw[edge] (q) to [bend right](y);
\draw[edge] (w) to (q);
\draw[edge] (r) to (y);
\draw[edge] (w) to [bend right](r);
\end{tikzpicture}
\end{center}
\end{minipage}
\caption{(a) The uncolored digraph $N(C_2)$ when $|V(C_2)| = 3$. (b) An acyclic 2-coloring of $N(C_2)$ when $w_1$ and $w_2$ are colored the same color. (c) An acyclic 2-coloring of $N(C_2)$ when $w_1$ and $w_2$ are colored different colors.}
\label{fig:2coloring}
 \end{figure}

Hence we can find a $v \in V(C_2)$ with $m+1$ in-neighbors or $m+1$ out-neighbors in $V(C_2)$. We let $u_n' = v$, and let the $m+1$ in-neighbors or out-neighbors of $v$ in $V(C_2)$ be $u_1', \ldots, u_{m+1}'$. We finally mark all of $u_1, \ldots, u_h$; notice that the subgraph induced by the marked vertices, namely $N(C_1)$, is weakly connected.

We next repeat the above process with our choice of $u_1', \ldots, u_{m+1}', u_n'$. Notice that the marked vertices must all belong to the same weakly connected component of $D_0' := D - \{u_1', \ldots, u_{m+1}'\}$, which we call $C_1'$. We then find a second weakly connected component of $D_0$, $C_2'$, and notice that by the same reasoning as above, there is some $v' \in V(C_2')$ with at least $m+1$ in-neighbors or $m+1$ out-neighbors in $C_2'$. We let $u_n'' = v'$, and let the $m+1$ in-neighbors or out-neighbors of $v$ in $C_2'$ be $u_1'', \ldots, u_{m+1}''$. We finally mark all vertices of $N(C_1')$, noting that we mark at least 1 vertex, namely all vertices in $s(C_1')$, for the first time and the subgraph induced by the marked vertices, namely $N(C_1')$, is weakly connected.

Since at least 1 new vertex is being marked with each iteration of the process, it must eventually end at some step $t$. That is, we can eventually find $u_1^{(t)}, \ldots, u_{m+1}^{(t)}, u_n^{(t)}$ so that all vertices in $D_0^{(t)} = D - \{u_1^{(t)}, \ldots, u_{m+1}^{(t)}\}$ are marked, meaning that $D_0^{(t)}$ is weakly connected. This is a contradiction to our original assumption.
\end{proof}



%\begin{lemma}
%\label{lem:critvertex}
%Suppose $v$ is a critical vertex in a digraph $D$, and $\chi_A(D) = k$. Then $d^+(v) \geq k-1$ and $d^-(v) \geq k-1$.
%\end{lemma}

%\begin{proof}
%Suppose for the purpose of contradiction that $d^+(v) < k-1$. We will show that we can find an acyclic $(k-1)$- coloring of $D$, a contradiction to the $k$-criticality of $D$. Since $v$ is $k$-critical, we can find an acyclic $(k-1)$-coloring of $D - v$.  At least one color class $c$ must be represented in less than $1$ out-neighbor of $v$. Now we color $v$ color $c$, and claim that the subgraph $H$ induced by all vertices of color $c$ is acyclic. To show this, notice that any cycle in $c$ must contain $v$. However, $v$ either contains no in-neighbors or out-neighbors of the same color, a contradiction.

%We can use the same proof to show that $d^-(v) \geq k-1$.
%\end{proof}



Theorem \ref{thm:kmcritical} states that the in-degree and out-degree of every vertex cannot be too small in a $(k, m)$-critical oriented graph.

\begin{theorem}
\label{thm:kmcritical}
Suppose that $m \geq 1$ and $D$ is a $(k, m)$-critical oriented graph in which each vertex $v$ satisfies $d^+(v) = d^-(v) = (k-1)m$. Then $k \leq 2$.% if $m > 1$, and $k \leq 2$ if $m = 1$.
\end{theorem}
Theorem \ref{thm:kmcritical} is of particular interest since it generalizes the following theorem of Mohar, who proved the case $m = 1$, which is a statement about acyclic colorings.

\begin{theorem}[Mohar \cite{mohar_eigen_2009}]
If $D$ is a $(k, 1)$-critical oriented graph in which each vertex $v$ satisfies $d^+(v) = d^-(v) = k-1$, then $k \leq 2$.
\end{theorem}

We now prove Theorem $\ref{thm:kmcritical}$, using Lemmas \ref{lem:2separator} and \ref{lem:trivial}.

\begin{proof}[Proof of Theorem \ref{thm:kmcritical}] We assume that $k \geq 3$ for the purpose of contradiction and create a linear ordering of the vertices of $D$, as follows. Pick a $u_n$ and choose $m + 1$ of its out-neighbors (or in-neighbors) $u_1, u_2, \ldots, u_{m+1}$, so that the digraph  $D - \{u_1, \ldots, u_{m+1}\}$ is weakly connected. This construction is possible by Lemma \ref{lem:2separator}. Let $D' = D - \{u_1, \ldots, u_{m+1}\}$. Now, since $u_n$ has $(k-1)m$ in-neighbors (or out-neighbors), there is some $u_{n-1} \in D'$ apart from $u_1, u_2, \ldots u_{m+1}$ such that $u_n$ is an out-neighbor or in-neighbor of $u_{n-1}$. Thus, $u_{n-1}$ has at most $(k-1)m - 1$ out-neighbors (or in-neighbors) in $D' - u_n$. Now continue in a similar manner, using the weakly connectedness of $D'$ to find $\{u_{m+2}, \ldots, u_{n-1}\}$ such that each of these vertices $v_i$ ($m+2 \leq i \leq n-1$) has out-degree or in-degree less than $(k-1)m$ in $D - \{u_{i+1}, \ldots, u_n\}$.

 %Specifically, for $n-1 \geq i \geq 3$, find a vertex $u_i \neq u_1, u_2, \ldots, u_{m+1}$ such that $u_i$ has some in-neighbor or out-neighbor among $\{u_{i+1}, \ldots, u_n\}$. Thus, $u_i$ must have in-degree or out-degree less than $(k-1)m$ in the digraph $D - \{u_{i+1}, \ldots, u_n\}$. Finding $u_i$, however, is possible if and only if there is some edge between $\{u_{i+1}, \ldots, u_n\}$ and $\{u_{m+2}, \ldots, u_i\}$. This is true for all $i$, since by construction, the subgraph induced by $\{u_{m+2}, \ldots, u_n\}$ is weakly connected.

We now color the vertices of $D$ as follows: we give $u_1, u_2, \ldots, u_{m+1}$ the same color; at this point, the coloring of $\{u_1, \ldots, u_{m+1}\}$ is $(k-1,m)$-degenerate since each vertex among $u_1, \ldots, u_{m+1}$ has less than $m$ in-neighbors or out-neighbors. Then for $m+2 \leq i \leq n-1$, we start with a $(k-1,m)$-degenerate coloring of $\{u_1, \ldots, u_{i-1}\}$ and extend this coloring to $u_i$. This is possible since in the subgraph of $D$ induced by $\{u_1, \ldots, u_i\}$, $u_i$ has in-degree or out-degree less than $(k-1)m$. Therefore, in the $(k-1, m)$-degenerate coloring of $\{u_1, \ldots, u_{i-1}\}$, one of the color classes contains fewer than $m$ in-neighbors or out-neighbors of $u_i$. We finally extend the $(k-1, m)$-degenerate coloring of $\{u_1, \ldots, u_{n-1}\}$ to $u_n$.  This is possible since $u_n$ has $m+1$ in-neighbors or out-neighbors, namely $u_1, \ldots, u_{m+1}$, of the same color, but exactly $(k-1)m$ in-neighbors and out-neighbors in total, so we can find a color represented among fewer than $m$ in-neighbors or out-neighbors of $u_n$, and color $u_n$ this color.

At the end of the process, we claim that each color class $c$ is $m$-degenerate. To show this, for any color class $c$ and  subset $S$ of the vertices colored $c$, pick $u_i \in S$ so that $i$ is as large as possible. Then since $u_i$ is the vertex in $S$ that was colored last, $u_i$ has at most $m-1$ in-neighbors or out-neighbors in $S$, completing the proof.
%At the end of the process, we claim that each color class is acyclic. To show this, notice that each vertex either shares no in-neighbors or out-neighbors with another vertex of its color. Therefore, it is impossible to have a cycle where all vertices have the same color.
\end{proof}

%To make notation simpler, we define $f(m)$ by $f(m) = 3$ if $m = 1$ and $f(m) =4$ if $m > 1$. 

Lemma \ref{lem:brooksdeg} uses Lemma \ref{lem:critvertex} to extend Theorem \ref{thm:kmcritical} to digraphs that are not $(k, m)$-critical. Intuitively, this is possible because $(k, m)$-critical digraphs are the worst case for finding an $m$-degenerate coloring with few colors.

\begin{lemma}
\label{lem:brooksdeg}
Suppose that $m \geq 1$, $\chi_m(D) = k + 1$, for some integer $k \geq 2$, and that $D$ is an oriented graph. Then $\bar{\Delta}(D) >   km$.
\end{lemma}
\begin{proof}
Fix $m \geq 1$.
Suppose for the purpose of contradiction that for some $k \geq 2$, there is an oriented graph $D$ with as few vertices as possible, such that $\chi_m(D) = k+1$ and $\bar{\Delta}(D) \leq km$.  Notice that if $D$ were not $(k+1, m)$-critical, we could remove some vertex $v$ to form $D' = D - v$, and we would have $\chi_m(D') = k+1$ and $\bar{\Delta}(D') \leq \bar{\Delta}(D) \leq km$. This contradicts the fact that $D$ has as few vertices as possible such that $\bar{\Delta}(D) \leq km$ holds. Hence $D$ is $(k+1, m)$-critical. 

By Lemma \ref{lem:critvertex}, for each $v \in V(D)$, we have that $d^+(v) \geq km$ and $d^-(v) \geq km$. In order to have $\bar{\Delta}(D) \leq km$, we must have $d^+(v)  = d^-(v) = km$ for all $v \in V(D)$. But then by Theorem \ref{thm:kmcritical}, we have that $k+1 \leq 2$, contradicting the fact  that $k+1 \geq 3$.
\end{proof}

The following corollary  follows from Lemma \ref{lem:brooksdeg}. It is a directed analogue of a theorem of Borodin \cite{borodin_decomposition_1976}.

\begin{corollary}
\label{cor:brookscor}
If $D$ is an oriented graph such that %$\bar{\Delta}(D) > km$, and if 
$\bar{\Delta}(D) \geq 2m$, then $\chi_m(D) \leq \left \lceil \frac{\bar{\Delta}(D)}{m}\right\rceil$.% **** something wrong here
\end{corollary}
\begin{proof}
Let $k = \left\lceil \frac{\bar{\Delta}(D)}{m} \right\rceil$. Then $k \geq 2$. If $\chi_m(D) \geq k + 1$, then by Lemma \ref{lem:brooksdeg}, $\bar{\Delta}(D) > km$, meaning that $\frac{\bar{\Delta}(D)}{m} > k$, so it is impossible that $k = \left\lceil \frac{\bar{\Delta}(D)}{m} \right\rceil$.
\end{proof}

%WRONG:By taking $m = 1$ in Corollary $\ref{cor:brookscor}$, and noting that $\chi_A(D)$ must be an integer, we have the following.
%\begin{corollary}
%\label{cor:brookscor2}
%If $D$ is an oriented graph such that $\bar{\Delta}(D) \geq 2$, then $\chi_A(D) \leq \lfloor \bar{\Delta}(D) \rfloor$.
%\end{corollary}

%\begin{lemma}
%\label{lem:brooksdeg}
%Suppose that $\chi(D) = k+1 \geq 3$, for some integer $k$, and that $D$ is an oriented graph. Then it is impossible that $\bar{\Delta}(D) \leq k$.
%\end{lemma}
%\begin{proof}
%Assume for the purpose of contradiction that for some $k \geq 3$, we have an oriented graph $D$ such that $\bar{\Delta}(D) \leq k$. Then by removing vertices until the chromatic number of $D$ decreases, we can assume that $D$ is $(k+1)$-critical. Thus, by Lemma \ref{lem:critvertex}, we must have that for each $v \in D$, $d^+(v) \geq k$ and $d^-(v) \geq k$. In order to have $ \bar{\Delta}(D) \leq k$, we need $d^+(v) = d^-(v) = k$. But, then, by Lemma \ref{lem:kmcritical}, we must have $k < 3$.
%\end{proof}
% Lemma \ref{lem:brooksdeg} implies that $\chi(D) \leq  \lceil \bar{\Delta}(D)\rceil$.

To prove Theorem \ref{thm:fracdelta}, we also use a theorem of Lov\' asz \cite{lovasz_on_1966}, which states that the vertices of a graph can be decomposed into sets so that the sum of the maximal degrees of all the sets is less than the maximal degree of the graph.



\begin{theorem}[Lov\' asz \cite{lovasz_on_1966}]
\label{thm:lovasz}
For an undirected graph $G$, suppose that for some $s \geq 1$ and positive integers $\Delta_1, \ldots, \Delta_s$, we have $\Delta(G) = (s-1) + \sum_{i = 1}^s \Delta_i$. Then there is a covering of $V(G)$ with $s$ subgraphs $G_i$ $(1 \leq i \leq s)$, so that $\Delta(G_i) \leq \Delta_i$ for $1 \leq i \leq s$.
\end{theorem}

We deduce as a corollary of Theorem \ref{thm:lovasz} a version for directed graphs. %To do so, we need an analogue of maximal degree in undirected graphs. Recall that $\bar{\Delta}(D)$ is the maximum, over all vertices $v$ of $D$, of the average of the out-degree and the in-degree of $v$.

%be the maximum, over all vertices $v$ of $D$, of the minimum of the out-degree and the in-degree of $v$.

\begin{corollary}
\label{cor:dirlov}
Given a digraph $D$, $s \geq 1$, and rational numbers $\bar{\Delta}_1, \ldots, \bar{\Delta}_s \geq 1$ so that for $1 \leq i \leq s$, $2\bar{\Delta}_i$ is an integer, suppose $\bar{\Delta}(D) =  \frac{s-1}{2} + \sum_{i = 1}^s \bar{\Delta}_i$. Then there is a covering of $V(D)$ with $s$ subgraphs $D_i$ $(1 \leq i \leq s)$ such that $\bar{\Delta}(D_i) \leq \bar{\Delta}_i$.
\end{corollary}

\begin{proof}
Given a digraph $D$, consider the underlying undirected graph $G$. Notice that $\Delta(G) = 2 \bar{\Delta}(D)$.  By Theorem \ref{thm:lovasz}, we can partition $G$ into vertex-disjoint subgraphs $G_1, \ldots, G_s$, so that the maximum total degree in $G_i$ is at most $2\bar{\Delta}_i$. For $1 \leq i \leq s$, we let $D_i$ be the directed subgraph of $D$ induced by $V(G_i)$. Thus, for $1 \leq i \leq s$, $\bar{\Delta}(D_i) \leq \bar{\Delta}_i$.
\end{proof}

We now prove Theorem \ref{thm:fracdelta}, using Lemma \ref{lem:brooksdeg} and Corollary \ref{cor:dirlov}  to find an upper bound on $\chi_m(D)$.


\begin{proof}[Proof of Theorem \ref{thm:fracdelta}]
Set
\begin{equation}
s = \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{2m + 1/2} \right\rfloor, \quad r = \bar{\Delta}(D) + 1/2 - s(2m + 1/2). \nonumber
\end{equation} 
 Then $\bar{\Delta}(D) = \frac{s}{2} + \left(\sum_{i = 1}^s 2m\right) + (r - \frac{1}{2}) $, meaning that, by Corollary \ref{cor:dirlov}, the vertices of $D$ can be covered with $s + 1$ subgraphs $D_1, \ldots, D_{s+1}$, which satisfy:
\begin{equation}
\bar{\Delta}(D_i) \leq
\begin{cases}
2m \quad\mbox{ if }\quad 1 \leq i \leq s\\
r - \frac{1}{2} \quad \mbox{ if } \quad i = s+1.
\end{cases}\nonumber
%\bar{\Delta}(D_i) \leq 2m & : & 1 \leq i \leq s\nonumber\\
%\bar{\Delta}(D_i) \leq r-\frac{1}{2} & : & i = s+1\nonumber.
\end{equation}
By Lemma \ref{lem:brooksdeg}, if $\chi_m(D_i) \geq 3$, then we would have that $\bar{\Delta}(D_i) > 2m$. Moreover, recalling the trivial bound that $\chi_m(D) \leq \left\lfloor \frac{\bar{\Delta}(D)}{m}\right \rfloor + 1$, we have
\begin{equation}
\chi_m(D_i) \leq \begin{cases}
2 \quad \mbox{ if } \quad 1 \leq i \leq s\\
1 + \left\lfloor \frac{\left(r-1/2\right)}{m}\right\rfloor \quad \mbox{ if } \quad i = s + 1 \nonumber.
\end{cases}
%\chi_m(D_i) \leq 2 & : &1\leq i \leq s\nonumber\\
%\chi_m(D_i) \leq 1 + \left\lfloor \left(r-1/2\right)/m\right\rfloor& : & i = s+1\nonumber.
\end{equation}
We thus have
\begin{eqnarray}
\chi_m(D)& \leq& \sum_{i = 1}^{s+1} \chi_m(D_i)\nonumber\\
&\leq& 2 s + \lfloor (r - 1/2)/m \rfloor + 1 \nonumber\\
&=& 2 \cdot \left\lfloor \frac{\bar{\Delta} + 1/2}{2m + 1/2} \right\rfloor + \left \lfloor \frac{\bar{\Delta}(D) - (2m + 1/2) \cdot \left\lfloor \frac{\bar{\Delta} + 1/2}{2m + 1/2} \right\rfloor}{m}\right\rfloor + 1\nonumber\\
&=& \left\lfloor \frac{\bar{\Delta}(D)}{m} -\left(\frac{2m + 1/2}{m} -2 \right)  \left\lfloor \frac{\bar{\Delta} + 1/2}{2m + 1/2} \right\rfloor\right\rfloor + 1\nonumber\\
&=& \left\lfloor \frac{\bar{\Delta}(D)  -\left(\frac{1}{2} \right)  \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{2m + 1/2} \right\rfloor}{m}\right\rfloor + 1\nonumber.
\end{eqnarray}
%Because $t/m$ is an integer,
%%\begin{equation}
%%\chi_1(D) \leq \left\lfloor \bar{\Delta}(D)  -\left(\frac{1}{2} \right)  \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{7/2} \right\rfloor\right\rfloor + 1\nonumber.
%%\end{equation}
%%In the case $m = 2, 3$, we have $t = 2m$, so:
%%\begin{equation}
%%\chi_2(D) \leq \left\lfloor \frac{\bar{\Delta}(D)  -\left(\frac{1}{2} \right)  \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{2m + 1/2} \right\rfloor}{m}\right\rfloor + 1\nonumber.
%%\end{equation}
%%For $m > 3$, we have $t = m$, and so:
%\begin{equation}
%\chi_m(D) \leq \left\lfloor \frac{\bar{\Delta}(D)  -\left(\frac{1}{2} \right)  \left\lfloor \frac{\bar{\Delta}(D) + 1/2}{t + 1/2} \right\rfloor}{m}\right\rfloor + 1\nonumber.
%\end{equation}
\end{proof}


\section{Better bounds for $m = 1$ with improved decomposition lemma}
\label{sec:betbounds}
In this section, we show that the bounds in Theorem \ref{thm:lovasz} can be improved for any digraph which does not contain any of the graphs shown in Figure \ref{fig:avoid} as an induced subgraph. This leads to improvements to the bounds in Theorem \ref{thm:fracdelta} in the case $m = 1$ for these classes of digraphs.  We first introduce some notation. Given disjoint sets of vertices $V_1$ and $V_2$ which belong to a digraph $D$, we let $E(V_1, V_2)$ be the set of all edges which point from a vertex in $V_1$ to a vertex in $V_2$. Moreover, we define $e(V_1, V_2) = |E(V_1, V_2)|$. Finally, given a vertex $u$, we define $d_{V_1}^+(u)$ as the number of out-neighbors of $u$ in $V_1$, $d_{V_1}^-(u)$ as the number of in-neighbors of $u$ in $V_1$, and $\bar{d}_{V_1}(u) = \frac{d_{V_1}^+(u) + d_{V_1}^-(u)}{2}$.

\begin{figure}

\begin{minipage}[b]{0.22\linewidth}
\begin{center}
$F_1$\\
\begin{tikzpicture}[thick,scale=0.8,->,shorten >=2pt]
    \draw (0,0) node {} -- (3,0) node {};
    \draw (3,0) node {} -- (3,3) node {};
    \draw (0,0) node {} -- (0,3) node {};
    \draw (0,3) node {} -- (3,3) node {};

 
\end{tikzpicture}
\end{center}

\end{minipage}
\hspace{0.01cm}
\begin{minipage}[b]{0.22\linewidth}
\begin{center}
$F_2$\\
\begin{tikzpicture}[thick,scale=0.8,->,shorten >=2pt]
    \draw (0,0) node {} -- (3,0) node {};
    \draw (3,0) node {} -- (3,3) node {};
    \draw (0,0) node {} -- (0,3) node {};
    \draw (0,3) node {} -- (3,3) node {};
    \draw (3,0) node {} -- (0,3) node {};

 
\end{tikzpicture}
\end{center}
\end{minipage}
\hspace{.01cm}
\begin{minipage}[b]{0.25\linewidth}
\begin{center}
$G_1$\\
\begin{tikzpicture}[thick,scale=0.8,->,shorten >=2pt]
    \draw (0,0) node {} -- (3,0) node {};
    \draw (3,0) node {} -- (3,3) node {};
    \draw (0,0) node {} -- (0,3) node {};
    \draw (0,3) node {} -- (3,3) node {};
    \draw (3,3) node {} -- (0,0) node {};

 
\end{tikzpicture}
\end{center}
\end{minipage}
\hspace{.01cm}
\begin{minipage}[b]{0.22\linewidth}
\begin{center}
$G_2$\\
\begin{tikzpicture}[thick,scale=0.8,->,shorten >=2pt]
    \draw (0,0) node {} -- (3,0) node {};
    \draw (3,0) node {} -- (3,3) node {};
    \draw (0,0) node {} -- (0,3) node {};
    \draw (0,3) node {} -- (3,3) node {};
    \draw (3,0) node {} -- (0,3) node {};
    \draw (3,3) node {} -- (0,0) node {};
 
\end{tikzpicture}
\end{center}
\end{minipage}
\caption{The digraphs $F_1, F_2, G_1$, and $G_2$.}
\label{fig:avoid}
\end{figure}

We let $F_1, F_2, G_1$, and $G_2$ be the 4-vertex digraphs shown in Figure \ref{fig:avoid}. For simplicity, we say that {\it $D$ avoids $F$} if $D$ contains neither $F_1$ nor $F_2$ as an induced subgraph and that $D$ {\it avoids} $G$ is $D$ contains neither $G_1$ not $G_2$ as an induced subgraph.

Notice that in Theorem \ref{thm:fracdelta} for the case $m = 1$, we set most of the $\bar{\Delta}_i$ to 2 because it is not true that if $\bar{\Delta}(D_i) \leq 1$, then $\chi_A(D_i) = 1$. The following Lemma \ref{lem:modlov} shows that if $D$ avoids $F$ and $G$, then we can partition $D$ into vertex-disjoint subgraphs $D_1, \ldots, D_s$, so that for all $i$ where $\bar{\Delta}_i = 1$, $D_i$ does not contain an induced cycle, and therefore $\chi_A(D_i) = 1$. Notice that if the shortest directed cycle in $D$ is of length at least 4, then the constraint is relaxed to the condition that $D$ avoids $F$. The proof is similar to that of an undirected analogue proved by Catlin \cite{catlin_another_1978}. 

\begin{lemma}
\label{lem:modlov}
Suppose we are given a digraph $D$, and positive integers $s, \bar{\Delta}_1, \ldots, \bar{\Delta}_s$. If \mbox{$\bar{\Delta}(D) = (s-2)/2 + \sum_{i = 1}^s \bar{\Delta}_i$} and $D$ avoids $F$ and $G$, then there is a partition  of $V(D)$ into $s$ subgraphs $D_i$ ($1 \leq i \leq s$) so that $\chi_A(D_i) \leq \bar{\Delta}_i$.
%\item If \mbox{$\bar{\Delta}(D) = \sum_{i = 1}^s \bar{\Delta}_i + (s-1)$} and $D$ is Eulerian, then there is a partition of $V(D)$ into $s$ subgraphs $D_i$ ($1 \leq i \leq s$) so that $\bar{\Delta}(D_i) \leq \bar{\Delta}_i$.
%\item  If \mbox{$\bar{\Delta}(D) = \sum_{i = 1}^s \bar{\Delta}_i + (s-1)$}, $D$ avoids $F$, and $D$ is Eulerian, then  there is a partition  of $V(D)$ into $s$ subgraphs $D_i$ ($1 \leq i \leq s$) so that $\chi_A(D_i) \leq \bar{\Delta}_i$.
%\end{enumerate} %which contains neither $F_1$ nor $F_2$ as an induced subgraph and positive integer $s$, suppose that \mbox{$\bar{\Delta}(D) = \sum_{i = 1}^s \bar{\Delta}_i + (s-2)/2$}, where the $\Delta_i$ are positive integers. Then there is a partition of $V(D)$ into $s$ subgraphs $D_i$ ($1 \leq i \leq s$) so that $\chi_A(D_i) \leq \bar{\Delta}_i$.
\end{lemma}
\begin{proof}
Given a partition of $V(D)$ into $s$ subsets $V_1, \ldots, V_s$, define
\begin{equation}
f(V_1, \ldots, V_2) = \bar{\Delta}_1 |V_1| + \bar{\Delta}_2 |V_2|+ \cdots + \bar{\Delta}_s |V_s| + \sum_{1 \leq i < j \leq s} \frac{e(V_i, V_j) + e(V_j, V_i)}{2}\nonumber.
\end{equation}
We let $A$ be the set of all $i$ such that $\bar{\Delta}_i = 1$. Notice that if $i \in A$, then any directed cycle in $V_i$ must be both induced and a component of the subgraph induced by $V_i$. Following notation of Catlin \cite{catlin_another_1978}, we call any such directed cycle a {\it Brooks cycle}.
Now, choose a partition of the vertices of $D$ into subsets $V_1, \ldots, V_s$ so that, (i), $f(V_1, \ldots, V_s)$ is maximized, and (ii), the number of Brooks cycles is minimized, subject to (i). 

We first claim that any partition which maximizes $f$ has $\bar{\Delta}(D_i) \leq \bar{\Delta}_i$ for all $i$. Notice that for any $u \in V_1$, and for $2 \leq j \leq s$, we have
\begin{equation}
f(V_1, \ldots, V_s) - f(V_1 -u, V_2, \ldots, V_j + u, \ldots, v_s) \geq 0\nonumber,
\end{equation}
by maximality of $f$. But
\begin{eqnarray}
\label{eq:diff}
&&f(V_1, \ldots, V_s) - f(V_1 -u, V_2, \ldots, V_j + u \ldots, v_s)\\
 &=& \frac{e(V_1, V_j) + e(V_j, V_1) - (e(V_1 - u, V_j + u) + e(V_j + u, V_1 - u))}{2} + \bar{\Delta}_1 - \bar{\Delta}_j\nonumber\\
 &=& \frac{d_{V_j}^+(u) - d_{V_1}^-(u)}{2} + \frac{d_{V_j}^-(u) - d_{V_1}^+(u)}{2} + \bar{\Delta}_1 - \bar{\Delta}_j\nonumber\\
\label{eq:finalmove}
 &=& \bar{d}_{V_j}(u) - \bar{d}_{V_1}(u) + \bar{\Delta}_1 - \bar{\Delta}_j.
\end{eqnarray}
Therefore, for $1 \leq j \leq s$, we have
\begin{equation}
\label{eq:toavg}
\bar{d}_{V_1}(u) \leq \bar{\Delta}_1 - \bar{\Delta}_j + \bar{d}_{V_j}(u).
\end{equation}
By averaging (\ref{eq:toavg}) over all choices of $j$, $1 \leq j \leq s$, we obtain
\begin{equation}
\bar{d}_{V_1}(u) \leq \bar{\Delta}_1 - \frac{\sum_{j = 1}^s \bar{\Delta}_j}{s} + \frac{\bar{d}_G(u)}{s} = \bar{\Delta}_1 - \frac{\bar{\Delta}(D) - (s-2)/2}{s} + \frac{\bar{d}_G(u)}{s}\nonumber.
\end{equation}
But $\bar{d}_G(u) \leq \bar{\Delta}(D)$, so
\begin{equation}
\bar{d}_{V_1}(u) \leq \bar{\Delta}_1 + \frac{s-2}{2s}\nonumber.
\end{equation}
Since $2\bar{\Delta}_1$ and $2\bar{d}_{V_1}(u)$ are integers, we must have that $\bar{d}_{V_1}(u) \leq \bar{\Delta}_1$. Since $u$ can be any vertex in $V_1$, we have $
\bar{\Delta}(D_1) \leq \bar{\Delta}_1$. Moreover, we can repeat the above process with $V_1$ replaced by $V_i$, for $2 \leq i \leq s$, and we have that $\bar{\Delta}(D_i) \leq \bar{\Delta}_i$.


Therefore, if $\bar{\Delta}_i \geq 2$, that is, if $i \not\in A$, then by Lemma \ref{lem:brooksdeg}, we have that $\chi_A(D_i) \leq \bar{\Delta}(D_i) \leq \bar{\Delta}_i$. We now claim that since the partition $V_1, \ldots, V_{s}$ minimizes the total number of Brooks cycles subject to the fact that $f(V_1, \ldots, V_s)$ is maximized,  the total number of Brooks cycles is 0. For the purpose of contradiction, suppose there is some Brooks cycle $C_0 \subset V_i$ where $i \in A$, and let $v_0 \in V(C_0)$. If $\bar{d}_{V_j}(v_0) \geq \bar{\Delta}_j + \frac12$ for each $j \neq i$, then since $\bar{d}_{V_i}(v_0) = \bar{\Delta}_i = 1$,
\begin{equation}
\bar{d}(v_0) \geq \bar{\Delta}_i + \sum_{j \neq i} \left(\bar{\Delta}_j + \frac12\right) = \bar{\Delta}(D) + \frac12  > \bar{\Delta}(D)\nonumber,
\end{equation}
which is impossible. Hence there is some $j \neq i$ so that $\bar{d}_{V_j}(v_0) \leq \bar{\Delta}_j$. Thus, noting that $\bar{d}_{V_i}(u) = \bar{\Delta}_i$, and by equality of (\ref{eq:diff}) with (\ref{eq:finalmove}), moving $v_0$ from $V_i$ to $V_j$ does not decrease $f(V_1, \ldots, V_s)$. Moreover, since moving $v_0$ removes a Brooks cycle from $V_i$, it must create a Brooks cycle $C_1$ in $V_j$. Therefore, by our definition of Brooks cycle, $\bar{\Delta}_j = 1$, so $j \in A$. We then pick $v_1 \neq v_0$ such that $v_1 \in V(C_1)$, and repeat the process. 

Eventually, since the total number of vertices is finite, there must be some $V_i$ so that the process generates an infinite sequence of Brooks cycles in $V_i$, which we call $C_1', C_2', \ldots$. Since each of the steps in our process moves only a single vertex, we must be able to find Brooks cycles $C_p'$ and $C_q'$ that differ in only one vertex. Specifically, suppose that $a \geq 2$ and the vertices of $C_p'$ are $x_1, \ldots, x_a, x_p$ while the vertices of $C_q'$ are $x_1, \ldots, x_a, x_q$.

If $a = 2$, then the vertices $x_1, x_a, x_p$, and $x_q$ form an induced subgraph isomorphic to either $G_1$ or $G_2$, depending on whether there is an edge between $x_p$ and $x_q$. If $a \geq 3$, then since $C_p'$ and $C_q'$ are induced, there is no edge between $x_a$ and $x_1$, meaning that the vertices $x_1, x_a, x_p$, and $x_q$ form an induced subgraph isomorphic to either $F_1$ or $F_2$. In either case, we have a contradiction to the fact that $D$ is $F$-free and $G$-free.
%If we moreover know that the digirth of $D$ is at least 4, then $a \geq 3$, meaning that $D$ contains an induced subgraph isomorphic to either $F_1$ or $F_2$.

% there is some $k < l$ so that $C_k$ has a non-empty intersection with $C_l$, and there is no $k < j < l$ so that $C_k$ intersects $C_j$. Suppose $v_{l-1}$ is the vertex moved in to create $C_l$, and $v_k$ is the vertex moved out to destroy $C_k$. Then $C_k$ and $C_l$ must overlap in a directed path, suppose $x_1, \ldots, x_t$, and we must have $x_tv_k, v_kx_1, x_tv_{l-1}, v_{l-1}x_1 \in E(D)$. Since $v_{l-1} \neq v_k$, $D$ must contain an induced subgraph isomorphic to $F_1$ or $F_2$, formed by the vertices $x_1, x_t, v_{l-1}, v_k$.

Thus there are no Brooks cycles, meaning that for $i \in A$, $D_i$ is acyclic, so $\chi_A(D_i) = 1 = \bar{\Delta}_i$ for all $i \in A$.
\end{proof}

Our main theorem of this section improves the bound of $\chi_A(D) \leq \frac{4}{5} \cdot \bar{\Delta}(D) + o(\bar{\Delta}(D))$ in Corollary $\ref{cor:acyclic}$ to $\chi_A(D) \leq \frac{2}{3} \cdot \bar{\Delta}(D) + o(\bar{\Delta}(D)$ for oriented graphs $D$ which avoid $F$ and $G$.

\begin{theorem}
Suppose $D$ is an oriented graph which avoids $F$ and $G$.  Then 
\begin{equation}\chi_A(D) \leq \left\lfloor \frac{2}{3} \cdot \bar{\Delta}(D) + 1/2\right\rfloor + 1.\nonumber
\end{equation}
\end{theorem}

\begin{proof}
 Set
\begin{equation}
s = \left\lfloor \frac{\bar{\Delta}(D) + 1}{3/2} \right\rfloor, \quad r = \bar{\Delta}(D) + 1 - 3/2s\nonumber.
\end{equation} 
Then $\bar{\Delta}(D) = (r-1) + \frac{s}{2} + \sum_{i = 1}^s 1$, meaning that, by Lemma \ref{lem:modlov}, the vertices of $D$ can be covered with $s + 1$ subgraphs $D_1, \ldots, D_{s+1}$, which satisfy:
\begin{equation}
\chi_A(D_i) \leq 
\begin{cases}
1 \quad \mbox{ if } \quad 1 \leq i \leq s \\
\left\lfloor r-\frac{1}{2}\right\rfloor + 1 \quad \mbox{ if } \quad i = s+ 1.\nonumber
\end{cases}
%\chi_A(D_i) \leq 1 & : & 1 \leq i \leq s\nonumber\\
%\chi_A(D_i) \leq \left\lfloor r-\frac{1}{2}\right\rfloor + 1 & : & i = s+1\nonumber.
\end{equation}
Thus
\begin{eqnarray}
\chi_A(D) &\leq& \sum_{i = 1}^{s+1} \chi_A(D_i)\nonumber\\
&\leq& s + \left \lfloor \bar{\Delta}(D) + 1/2 - 3/2s \right\rfloor + 1\nonumber\\
&=& \left \lfloor \frac{\bar{\Delta}(D) + 1}{3/2} \right\rfloor +  \left \lfloor \bar{\Delta}(D) + 1/2 - 3/2 \left\lfloor \frac{\bar{\Delta}(D) + 1}{3/2} \right\rfloor \right\rfloor + 1\nonumber\\
&=& \left\lfloor \bar{\Delta}(D) + 1/2 -  1/2 \left\lfloor \frac{\bar{\Delta}(D) + 1}{3/2} \right\rfloor \right\rfloor + 1\nonumber\\
&\leq& \lfloor 2/3 \cdot \bar{\Delta}(D) + 1/2 \rfloor + 1\nonumber.
\end{eqnarray}
\end{proof}


\section{Concluding remarks}
In this paper, we have proved an upper bound on a generalization of the acyclic chromatic number, the $m$-degenerate chromatic number. Moreover, the special case of $m = 1$ gives a bound on the acyclic number which significantly improves current bounds. However, the bound in Theorem \ref{thm:fracdelta} differs from the conjectured bound in Conjectures \ref{conj:everything} by a factor of $\log \bar{\Delta}(D)$. It seems that a new technique is necessary to obtain the additional factor of $\log \bar{\Delta}(D)$, if it is indeed correct. Moreover, it seems that Conjecture \ref{conj:everything} can be extended to the $m$-degenerate chromatic number.
\begin{conjecture}
If $m$ is a positive integer and $c$ is a constant which does not depend on $m$, then every oriented graph $D$ has $\chi_m(D) \leq (c + o(1))\frac{(\bar{\Delta}(D)/m)}{\log (\bar{\Delta}(D)/m)}$.
\end{conjecture}

We finally note that the bounds obtained in this paper were all phrased in terms of $\bar{\Delta}(D)$. By the arithmetic mean - geometric mean inequality, for any digraph $D$, we have $\widetilde{\Delta}(D) \leq \bar{\Delta}(D)$, meaning that bounds phrased in terms of $\widetilde{\Delta}(D)$ would be slightly stronger. It does not seem that our methods can produce bounds which would hold with $\bar{\Delta}(D)$ replaced by $\widetilde{\Delta}(D)$. However, most graphs which are interesting for the problem of acyclic chromatic number have the in-degree and out-degree of the vertices approximately equal, meaning that $\bar{\Delta}(D) \approx \widetilde{\Delta}(D)$.

\section{Acknowledgements}
I would like to thank David Rolnick for his helpful discussions and review of the paper. I would also like to thank Jacob Fox for suggesting the direction of research and Tanya Khovanova for helpful suggestions and review. I thank Pavel Etingof, David Jerison, and Slava Gerovitch for coordinating the research, and John Rickert for helpful review. Finally I would like to thank the Center for Excellence in Education,  the Research Science Institute, and the MIT Math Department for their support.
\bibliographystyle{plain}

\bibliography{colorings}

\end{document}
chromatic_number_max_degree4.bbl
\begin{thebibliography}{10}

\bibitem{acyclic_aharoni_2008}
Ron Aharoni, Eli Berger, and Ori Kfir.
\newblock Acyclic systems of representatives and acyclic colorings of digraphs.
\newblock {\em Journal of Graph Theory}, pages 177--189, 2008.

\bibitem{ben_size_2012}
Ido Ben-Eliezer, Michael Krivelevich, and Benny Sudakov.
\newblock The size {R}amsey number of a directed path.
\newblock {\em Journal of Combinatorial Theory, Series B}, 102:~743--755, 2012.

\bibitem{circular_bokal_2004}
Drago Bokal, Gasper~Fijav\v z, Martin Juvan, P.~Mark Kayll, and Bojan Mohar.
\newblock The circular chromatic number of a digraph.
\newblock {\em Journal of Graph Theory}, pages 227--240, 2004.

\bibitem{borodin_decomposition_1976}
Oleg Borodin.
\newblock On decomposition of graphs into degenerated subgraphs.
\newblock {\em Diskretnyj Analiz}, 28, 1976.

\bibitem{borodin_acyclic_1979}
Oleg Borodin.
\newblock On acyclic colorings of planar graphs.
\newblock {\em Discrete Mathematics}, 25:~211--236, 1979.

\bibitem{borodin_upper_1977}
Oleg Borodin and Alexandr Kostochka.
\newblock On an upper bound of a graph's chromatic number, depending on the
  graph's degree and density.
\newblock {\em Journal of Combinatorial Theory, Series B}, 23:~247--250, 1977.

\bibitem{brooks_coloring_1941}
Rowland Brooks.
\newblock On coloring the nodes of a network.
\newblock {\em Mathematical Proceedings of the Cambridge Philosophical
  Society}, 37:~194--197, 1941.

\bibitem{catlin_another_1978}
Paul Catlin.
\newblock Another bound on the chromatic number of a graph.
\newblock {\em Discrete Mathematics}, 24:~1--6, 1978.

\bibitem{catlin_bound_1978}
Paul Catlin.
\newblock A bound on the chromatic number of a graph.
\newblock {\em Discrete Mathematics}, 22:~81--83, 1978.

\bibitem{chen_coloring_2014}
Zhibin Chen, Jie Ma, and Wenan Zang.
\newblock Coloring digraphs with forbidden cycles.
\newblock {\em arXiv}, 1403.8127, 2014.

\bibitem{strengthened_harut_2011}
Ararat Harutyunyan and Bojan Mohar.
\newblock Strengthened {B}rooks' theorem for digraphs of girth at least three.
\newblock {\em Electronic Journal of Combinatorics}, 18:~P195, 2011.

\bibitem{two_harut_2012}
Ararat Harutyunyan and Bojan Mohar.
\newblock Two results on the digraph chromatic number.
\newblock {\em Discrete Mathematics}, 312(10):~1823--1826, 2012.

\bibitem{jamall_brooks_2011}
Mohammad~Shoaib Jamall.
\newblock A {B}rooks' theorem for triangle-free graphs.
\newblock {\em arXiv}, 1106.1958, 2011.

\bibitem{johannson_asymptotic}
A.~Johannson.
\newblock Asymptotic choice number for triangle free graphs.
\newblock {\em {U}npublished}.

\bibitem{digraph_keevash_2013}
Peter Keevash, Zhentao Li, Bojan Mohar, and Bruce Reed.
\newblock Digraph girth via chromatic number.
\newblock {\em SIAM Journal on Discrete Mathematics}, 27(2):~693--696, 2013.

\bibitem{kim_brooks_1995}
Jeong~Han Kim.
\newblock On {B}rooks' theorem for sparse graphs.
\newblock {\em Combinatorics, Probability, and Computing}, 4(2):~97--132, 1995.

\bibitem{lovasz_on_1966}
L\'aszl\'o Lov\'asz.
\newblock On decomposition of graphs.
\newblock {\em Studia Scientiarum Mathematicarum Hungarica}, 1:~237--238, 1966.

\bibitem{mohar_eigen_2009}
Bojan Mohar.
\newblock Eigenvalues and colorings of digraphs.
\newblock {\em Linear Algebra and its Applications}, 432:~2273--2277, 2010.

\end{thebibliography}
