Erdős–Neumann-Lara conjecture on chromatic and dichromatic numbers

Let GG be a graph. An orientation of GG is a digraph with underlying graph GG and at most one arc between each pair of vertices. For a digraph DD, its dichromatic number vecχ(D)vec\chi(D) is the minimum number of colours in a vertex colouring whose colour classes induce acyclic subdigraphs; define

χ(G)=maxDχ(D),\vec\chi(G)=\max_D\vec\chi(D),

where the maximum is over all orientations DD of GG. Let χ(G)\chi(G) denote the chromatic number of GG.

Erdős–Neumann-Lara conjecture. For every integer kk there is an integer f(k)f(k) such that, for every graph GG, χ(G)f(k)\chi(G)\geq f(k) implies χ(G)k\vec\chi(G)\geq k.

This asks whether arbitrarily large chromatic number forces an orientation with arbitrarily large dichromatic number. The problem is open: f(1)=1f(1)=1 and f(2)=3f(2)=3 are possible, but it is unclear whether f(3)f(3) 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

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.