Acyclic number Θ(√(n log n)) oriented triangle-free
Conjecture 3 · arXiv:2403.02298
Status open high confidence
Conjecture 3 of arXiv:2403.02298 asserts that the minimum acyclic number over all oriented triangle-free graphs of order n satisfies $\vec{a}(n)=\Theta(\sqrt{n\log n})$. The source paper establishes matching lower bound $(\frac{1}{\sqrt{2}}-\varepsilon)\sqrt{n\log n}$ and upper bound $\frac{107}{8}\sqrt{n}\log n$, leaving a logarithmic gap; the authors conjecture the upper bound can be tightened to $C\sqrt{n\log n}$ via the triangle-free process. No subsequent paper resolving or significantly advancing this conjecture was found in a broad web search conducted through May 2026; the paper appeared in the Electronic Journal of Combinatorics (2025) without amendment to the conjecture's status.
Reviewer notes. No follow-up resolving the conjecture was found. The paper 2511.20246 ('Acyclic dichromatic number of oriented graphs', Nov 2025) introduces a related but distinct parameter and does not address this conjecture. The paper 2603.02947 ('Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths', Mar 2026) treats random regular digraphs and does not treat the triangle-free oriented setting. The source paper was published in Electronic Journal of Combinatorics v32i4p27 (2025).
Context
The paper establishes $\left(\frac{1}{\sqrt{2}}-\varepsilon\right)\sqrt{n\log n}\leq\vec{a}(n)\leq\frac{107}{8}\sqrt{n}\log n$, a logarithmic gap between lower and upper bounds. The authors believe the upper bound can be sharpened to $C\sqrt{n\log n}$ by analysing a suitable orientation of the triangle-free process $G_{\triangle}$.
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