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

About 11 years old · traced to

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)=max⁡Dχ⃗(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.

References

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.