A Note on Coloring Digraphs of Large Girth

Abstract

The digirth of a digraph is the length of a shortest directed cycle. The dichromatic number $\vec{\ddot{I}}‡(D)$ of a digraph $D$ is the smallest size of a partition of the vertex-set into subsets inducing acyclic subgraphs. A conjecture by Harutyunyan and Mohar states that $\vec{\ddot{I}}‡(D)\le \lceil \frac{\hat{I}}{”}4\rceil +1$ for every digraph $D$ of digirth at least $3$ and maximum degree $\hat{I}”$. The best known partial result by Golowich shows that $\vec{\ddot{I}}‡(D)\le \frac{2}{5}\hat{I}”+O(1)$. In this short note we prove for every $g\ge 2$ that if $D$ is a digraph of digirth at least $2g-1$ and maximum degree $\hat{I}”$, then $\vec{\ddot{I}}‡(D)\le (\frac{1}{3}+\frac{1}{3g})\hat{I}”+O_g(1)$. This improves the bound of Golowich for digraphs without directed cycles of length at most $10$.

note, 3 pages