\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Ararat Harutyunyan and Bojan Mohar}
%
%
\medskip
\noindent
%
%
{\bf Strengthened Brooks' Theorem for Digraphs of Girth at least Three}
%
%
\vskip 5mm
\noindent
%
%
%
%
Brooks' Theorem states that a connected graph $G$ of maximum
degree $\Delta$ has chromatic number at most $\Delta$, unless $G$
is an odd cycle or a complete graph. A result of Johansson shows
that if $G$ is triangle-free, then the chromatic number drops to
$O(\Delta / \log \Delta)$. In this paper, we derive a weak analog
for the chromatic number of digraphs. We show that every
(loopless) digraph $D$ without directed cycles of length two has
chromatic number $\chi(D) \leq (1-e^{-13}) \tilde{\Delta}$, where
$\tilde{\Delta}$ is the maximum geometric mean of the out-degree and
in-degree of a vertex in $D$, when $\tilde{\Delta}$ is sufficiently
large. As a corollary it is proved that there exists an absolute
constant $\alpha < 1$ such that $\chi(D) \leq \alpha (\tilde{\Delta} +
1)$ for every $\tilde{\Delta} > 2$.
\end{document}