Erdős–Neumann-Lara conjecture on chromatic and dichromatic numbers
Erdős–Neumann-Lara conjecture on chromatic and dichromatic numbers
Let be a graph. An orientation of is a digraph with underlying graph and at most one arc between each pair of vertices. For a digraph , its dichromatic number is the minimum number of colours in a vertex colouring whose colour classes induce acyclic subdigraphs; define
where the maximum is over all orientations of . Let denote the chromatic number of .
Erdős–Neumann-Lara conjecture. For every integer there is an integer such that, for every graph , implies .
This asks whether arbitrarily large chromatic number forces an orientation with arbitrarily large dichromatic number. The problem is open: and are possible, but it is unclear whether exists.
Sources & referencesView supporting material
Primary source
Ararat Harutyunyan, Lucas Picasarri-Arrieta and Gil Puig i Surroca, “On the list version of a conjecture of Erdős and Neumann-Lara”, arXiv:2603.01020 (2026).
Additional references
5 papers in this index state this conjecture (2015–2026). The statement above is taken from the most recent of them; the others are arXiv:2309.16565, arXiv:1708.02441, arXiv:1608.06981, arXiv:1510.05982.
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.