Aharoni–Berger–Kfir conjecture on acyclic sets in oriented graphs
Let be an oriented graph with vertices and edges or arcs, and let denote its largest acyclic set. Aharoni–Berger–Kfir conjecture.
For tournaments this predicts ; the bound is known up to a factor of , and whether this factor can be attained is a major open problem.
References
Primary source
Ararat Harutyunyan, Colin McDiarmid and Gil Puig i Surroca, “Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths”, arXiv:2603.02947 (2026).
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.