Erdős's conjecture on the dichromatic number of digon-free digraphs

Let DD be a digon-free digraph, meaning that no pair of opposite directed edges joins the same two vertices, and let Δ\Delta be its maximum total degree. Erdős's conjecture. There is an absolute constant such that

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

This is the directed analogue of logarithmic improvements over the maximum-degree bound for chromatic number. The paper presents it as a conjecture of Erdős and studies a corresponding list-coloring upper bound; no resolution is supplied in the given text.

Sources & referencesView supporting material

Primary source

Julien Bensmail, Ararat Harutyunyan and Ngoc Khang Le, “List coloring digraphs”, arXiv:1510.03578 (2015).

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.