Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.01020 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915935805243392 |
|---|---|
| author | Harutyunyan, Ararat Picasarri-Arrieta, Lucas Surroca, Gil Puig i |
| author_facet | Harutyunyan, Ararat Picasarri-Arrieta, Lucas Surroca, Gil Puig i |
| contents | 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 dichromatic number. The main tool in our result is the following theorem, which is an extension of an analogous result of Alon for the chromatic number: every graph of minimum degree $d$ admits an orientation such that the resulting digraph has list dichromatic number of order at least $\ln d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_01020 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the list version of a conjecture of Erdős and Neumann-Lara Harutyunyan, Ararat Picasarri-Arrieta, Lucas Surroca, Gil Puig i Combinatorics 05C15, 05C20, 05C69 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 dichromatic number. The main tool in our result is the following theorem, which is an extension of an analogous result of Alon for the chromatic number: every graph of minimum degree $d$ admits an orientation such that the resulting digraph has list dichromatic number of order at least $\ln d$. |
| title | On the list version of a conjecture of Erdős and Neumann-Lara |
| topic | Combinatorics 05C15, 05C20, 05C69 |
| url | https://arxiv.org/abs/2603.01020 |