Conjecture on the minimum acyclic number of oriented triangle-free graphs
For each positive integer , let be the minimum of over all oriented triangle-free graphs of order , where denotes the maximum size of an acyclic vertex set. Minimum acyclic number conjecture.
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
- 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.