The asymptotic coloring conjecture for oriented graphs with bounded cycle lengths

Let DD be an oriented graph with no directed cycle of length greater than ss, and let χ(D)\vec{\chi}(D) denote its dichromatic number.

Asymptotic coloring conjecture. As ss\rightarrow\infty,

χ(D)=O(slogs).\vec{\chi}(D)=O\left(\frac{s}{\log s}\right).

This conjecture predicts an asymptotic improvement over the bound χ(D)s/2\vec{\chi}(D)\leq \lceil s/2\rceil for oriented graphs of circumference at most ss. 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

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.