Aharoni–Berger–Kfir conjecture on acyclic sets in oriented graphs
Aharoni–Berger–Kfir conjecture on acyclic sets in oriented graphs
From papers
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.