Maximum dichromatic number of oriented triangle-free graphs
Conjecture 4 · arXiv:2403.02298
Status open high confidence
Conjecture 4 from arXiv:2403.02298 asserts $\vec{t}(n)=\Theta\sqrt{n/\log n}$ for the maximum dichromatic number of oriented triangle-free graphs on $n$ vertices. The paper itself establishes an upper bound $\vec{t}(n)\leq(\sqrt{2}+o(1))\sqrt{n/\log n}$ and a lower bound $\vec{t}(n)\geq\frac{8}{107}\frac{\sqrt{n}}{\log n}$, leaving a $\sqrt{\log n}$ gap on the lower side. No follow-up paper closing this gap or otherwise resolving the conjecture was found in the indexed literature.
Reviewer notes. No follow-up resolving Conjecture 4 was found. The conjecture follows from Conjecture 3 of the same paper (about $\vec{a}(n)$). The source paper has been published as Electronic Journal of Combinatorics vol. 32, issue 4, P4.27 (2025-11-03), URL https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i4p27. The paper arXiv:2511.20246 ('Acyclic dichromatic number of oriented graphs', Nov 2025) introduces a related but distinct parameter and does not address Conjecture 4.
Context
Conjecture 4 follows from Conjecture 3, since $\vec{t}(n)\geq n/\vec{a}(n)$ and $\vec{t}(n)\leq t(n)$. The paper establishes $\frac{8}{107}\frac{\sqrt{n}}{\log n}\leq\vec{t}(n)\leq\left(\sqrt{2}+o(1)\right)\sqrt{\frac{n}{\log n}}$, leaving a logarithmic gap on the lower side.
Notes. The LaTeX in the source appears to be missing parentheses around the $\Theta$ argument; reproduced verbatim as given.
Source paper
Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
Pierre Aboulker, Frédéric Havet, François Pirot, Juliette Schabanel · 2024-03-04
https://arxiv.org/abs/2403.02298