Erdős–Neumann-Lara conjecture for oriented graphs

Let DD be an oriented graph, and let Δ\Delta be the maximum degree of the underlying graph of DD. Let χ(D)\vec{\chi}(D) denote its dichromatic number. Erdős–Neumann-Lara conjecture. Every oriented graph DD satisfies

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

This is a directed analogue of Johansson's bound for triangle-free graphs and concerns the asymptotic relationship between dichromatic number and maximum degree. It remains open.

Sources & referencesView supporting material

Primary source

Ken-ichi Kawarabayashi and Lucas Picasarri-Arrieta, “Coloring digraphs with Δ-b colors”, arXiv:2607.06928 (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.