List Erdős–Neumann-Lara conjecture

Less than 1 year old · traced to 2026

Let $G$ be a graph. Its list chromatic number $\chi_{\ell}(G)$ is the least integer $r$ such that every assignment of lists of $r$ colours to the vertices admits a proper list colouring. For an orientation $D$ of $G$ , define its list dichromatic number $\vec\chi_{\ell}(D)$ analogously, using list colourings in which every colour class induces an acyclic digraph, and let

\vec\chi_{\ell}(G)=\max_D\vec\chi_{\ell}(D),

where the maximum is over all orientations $D$ of $G$ .

List Erdős–Neumann-Lara conjecture. For every integer $k$ there is an integer $f(k)$ such that, for every graph $G$ , $\chi_{\ell}(G)\geq f(k)$ implies $\vec\chi_{\ell}(G)\geq k$ .

The paper states that it proves this list version of the Erdős–Neumann-Lara conjecture, so the claim is resolved by the source's results.

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).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2026 preprint claims to prove the conjecture, but the proof has not been independently verified.

The conjecture asks whether sufficiently large list chromatic number forces arbitrarily large list dichromatic number. The retrieved preprint presents a proof of this implication.

2026 preprint claiming a proof

The paper claims that every graph of minimum degree $d$ satisfies $\vec{\chi}_{\ell}(G)\geq (\frac{1}{3}-o(1))\log_{2}d$ , and derives $\vec{\chi}_{\ell}(G)\geq (\frac{1}{3}-o(1))\log_{2}\chi_{\ell}(G)$ . It explicitly identifies this as a proof of the list Erdős–Neumann–Lara conjecture. A stated quantitative consequence is that, for sufficiently large $r$ , average degree at least $r^{7}2^{3r+17}$ implies $\vec{\chi}_{\ell}(G)\geq r$ . No independent verification, error report, withdrawal, or competing proof was found.

Current status (as of September 2026): The conjecture is claimed solved by the 2026 preprint, but its proof remains unverified in the retrieved record.

Sources

No solutions have been posted yet.