Erdős's conjecture on the dichromatic number of digon-free digraphs
Erdős's conjecture on the dichromatic number of digon-free digraphs
Let be a digon-free digraph, meaning that no pair of opposite directed edges joins the same two vertices, and let be its maximum total degree. Erdős's conjecture. There is an absolute constant such that
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
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.