Conjecture on the minimum acyclic number of oriented triangle-free graphs

About 2 years old · traced to

For each positive integer nn, let a⃗(n)\vec a(n) be the minimum of α⃗(D)\vec\alpha(D) over all oriented triangle-free graphs DD of order nn, where α⃗(D)\vec\alpha(D) denotes the maximum size of an acyclic vertex set. Minimum acyclic number conjecture.

a⃗(n)=Θ ⁣(nlog⁡n).\vec a(n)=\Theta\!\left(\sqrt{n\log n}\right).

The conjecture is motivated by the triangle-free process and would match the known lower bound up to constant factors, while improving the currently known upper bound asymptotically.

References

Primary source

Pierre Aboulker, Frédéric Havet, François Pirot and Juliette Schabanel, “Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order”, arXiv:2403.02298 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.