The asymptotic coloring conjecture for oriented graphs with bounded cycle lengths

Less than 1 year old · traced to

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 s→∞s\rightarrow\infty,

χ⃗(D)=O(slog⁡s).\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.

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.