The asymptotic coloring conjecture for oriented graphs with bounded cycle lengths
The asymptotic coloring conjecture for oriented graphs with bounded cycle lengths
Let be an oriented graph with no directed cycle of length greater than , and let denote its dichromatic number.
Asymptotic coloring conjecture. As ,
This conjecture predicts an asymptotic improvement over the bound for oriented graphs of circumference at most . The supplied source indicates that this statement has been proved, so it is recorded as solved.
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).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.