Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
<|reference_start|>Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order: 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} \leq \vec{a}(n) \leq \frac{107}{8} \sqrt n \log n$ and $\frac{8}{107} \sqrt n/\log n \leq \vec{t}(n) \leq (\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.<|reference_end|>
@article{aboulker2024minimum,
    title={Minimum acyclic number and maximum dichromatic number of oriented
  triangle-free graphs of a given order},
    author={Pierre Aboulker, Fr'ed'eric Havet, Franc{c}ois Pirot, Juliette
  Schabanel},
    journal={arXiv preprint arXiv:2403.02298},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.02298},
    primaryClass={math.CO cs.DM}
}