On the list version of a conjecture of Erdős and Neumann-Lara

Ararat Harutyunyan, Lucas Picasarri-Arrieta, Gil Puig i Surroca

arXivarxiv/2603.01020Mar 1, 2026math.COscore 0

The dichromatic number of a digraph $D$, denoted by $\vecχ(D)$, is the smallest number of colours required to colour the vertices of $D$ such that each colour class induces an acyclic digraph. A conjecture of Erdős and Neumann-Lara states that there exists a function $f(k)$ such that for every graph $G$ with $χ(G) \geq f(k)$ there is an orientation of $G$ such that the resulting digraph $D$ satisfies $\vecχ(D) \geq k$. We prove the list version of this conjecture: if $G$ has large list chromatic number then there is an orientation of $G$ such that the resulting digraph has large list…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2603.01020
curl -X POST /api/v1/records/arxiv/2603.01020/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.01020/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'