Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order

Abstract

Let $D$ be a digraph. Its acyclic number $\vec{\alpha }(D)$ is the maximum order of an acyclic induced subdigraph and its dichromatic number $\vec{\chi }(D)$ is the least integer $k$ such that $V(D)$ can be partitioned into $k$ subsets inducing acyclic subdigraphs. We study $\vec{a}(n)$ and $\vec{t}(n)$ which are the minimum of $\vec{\alpha }(D)$ and the maximum of $\vec{\chi }(D)$, respectively, over all oriented triangle-free graphs of order $n$. For every $\epsilon >0$ and $n$ large enough, we show $(1/\sqrt{2}-\epsilon )\sqrt{n\log n}\le \vec{a}(n)\le \frac{107}{8}\sqrt{n}\log n$ and $\frac{8}{107}\sqrt{n}/\log n\le \vec{t}(n)\le (\sqrt{2}+\epsilon )\sqrt{n/\log n}$. We also construct an oriented triangle-free graph on 25 vertices with dichromatic number~3, and show that every oriented triangle-free graph of order at most 17 has dichromatic number at most 2.

19 pages, 5 figures