pith. sign in

arxiv: 2603.01020 · v2 · submitted 2026-03-01 · 🧮 math.CO

On the list version of a conjecture of ErdH{o}s and Neumann-Lara

Ararat Harutyunyan , Lucas Picasarri-Arrieta , Gil Puig i Surroca This is my paper

Pith reviewed 2026-05-15 18:35 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1505C20
keywords list chromatic numberlist dichromatic numbergraph orientationErdős–Neumann-Lara conjectureminimum degreedigraph coloringacyclic coloring
0
0 comments X

The pith

If a graph has high list chromatic number, it admits an orientation with high list dichromatic number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves the list version of the Erdős and Neumann-Lara conjecture. Graphs whose list chromatic number is large enough have an orientation that produces a digraph whose list dichromatic number is also large. The central step is an extension of Alon's theorem: any graph of minimum degree d can be oriented so that its list dichromatic number is at least on the order of the natural logarithm of d. A sympathetic reader cares because the result ties undirected choosability directly to directed acyclic coloring under orientation.

Core claim

The authors prove that if the list chromatic number of an undirected graph G is large, then there exists an orientation of G such that the resulting digraph D has large list dichromatic number. The main tool is the theorem that every graph of minimum degree d admits an orientation whose list dichromatic number is at least on the order of ln d.

What carries the argument

The minimum-degree orientation theorem for list dichromatic number: every graph of minimum degree d admits an orientation with list dichromatic number at least ln d.

If this is right

  • If the list chromatic number of G is at least some function f(k), then G has an orientation with list dichromatic number at least k.
  • The original Erdős–Neumann-Lara conjecture holds whenever the chromatic number of G is large, since list chromatic number is at least chromatic number.
  • Any graph of minimum degree d has some orientation whose list dichromatic number grows at least logarithmically with d.
  • The list versions of the parameters behave quantitatively like the ordinary versions under orientation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same orientation technique may extend to other directed parameters such as list directed chromatic number.
  • Explicit constructions of the orientations might be obtainable from list-coloring algorithms.
  • The logarithmic bound suggests that high-degree graphs force directed acyclic colorings to scale with density even in the list setting.

Load-bearing premise

Every graph of minimum degree d admits an orientation whose list dichromatic number is at least on the order of ln d.

What would settle it

A graph of minimum degree d whose every orientation has list dichromatic number o(log d).

read the original abstract

The dichromatic number of a digraph $D$, denoted by $\vec{\chi}(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\H{o}s and Neumann-Lara states that there exists a function $f(k)$ such that for every graph $G$ with $\chi(G) \geq f(k)$ there is an orientation of $G$ such that the resulting digraph $D$ satisfies $\vec{\chi}(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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves the list version of the Erdős–Neumann-Lara conjecture: if a graph G has sufficiently large list chromatic number, then there exists an orientation D of G such that the list dichromatic number of D is also large. The central tool is an extension of Alon’s minimum-degree theorem, establishing that every graph of minimum degree d admits an orientation whose list dichromatic number is at least on the order of ln d; the proof of the conjecture then follows by relating list chromatic number to minimum degree and applying the tool.

Significance. If the result holds, it provides the first list-coloring analogue of the conjecture and supplies an explicit logarithmic lower bound via a probabilistic orientation argument. This strengthens the connection between list chromatic number and list dichromatic number, extending a classical result of Alon while preserving the same order of magnitude. The manuscript ships a complete, self-contained proof of the main tool rather than a sketch, which is a clear strength.

minor comments (3)
  1. §2: The notation for list dichromatic number (denoted vec χ_l(D)) is introduced without an explicit comparison to the ordinary list chromatic number; adding one sentence relating the two parameters would improve readability for readers outside digraph coloring.
  2. Theorem 1.3 (the main tool): The probabilistic argument uses a random orientation; the dependence on the choice of probability p = 1/2 is implicit but never stated explicitly, which could be clarified in one line.
  3. References: The citation to Alon’s 1990 paper is given only by year; adding the full bibliographic details (journal, volume, pages) would be helpful.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the clear summary of our results, and the recommendation to accept the manuscript. We are pleased that the extension of Alon's theorem and its application to the list version of the Erdős–Neumann-Lara conjecture were viewed favorably.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes its main result by proving an extension of Alon's minimum-degree theorem to the list dichromatic number setting, using an explicit probabilistic orientation argument detailed in the body. This extension serves as the load-bearing tool and is not reduced to a fitted parameter, self-definition, or prior self-citation; the list-version conjecture then follows directly from the relation between list chromatic number and minimum degree. All steps are independent of the target quantities by construction, with no renaming of known results or ansatz smuggling via citation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities are introduced. The argument rests on standard definitions of list coloring, orientations, and acyclicity together with the extension of Alon’s theorem.

axioms (1)
  • standard math Standard definitions and basic properties of list chromatic number, dichromatic number, and orientations of undirected graphs.
    The proof invokes these definitions to state the conjecture and the main theorem.

pith-pipeline@v0.9.0 · 5498 in / 1258 out tokens · 27263 ms · 2026-05-15T18:35:33.790876+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    N. Alon. Degrees and choice numbers.Random Structures & Algorithms, 16(4):364–368, 2000

    work page 2000

  2. [2]

    N. Alon, S. Cambie, and R. J. Kang. Asymmetric list sizes in bipartite graphs.Annals of Combinatorics, 25:913–933, 2021

    work page 2021

  3. [3]

    Alon and M

    N. Alon and M. Krivelevich. The choice number of random bipartite graphs.Annals of Combinatorics, 2:291–297, 1998

    work page 1998

  4. [4]

    Bensmail, A

    J. Bensmail, A. Harutyunyan, and N. K. Le. List coloring digraphs.Journal of Graph Theory, 87(4):492–508, 2018

    work page 2018

  5. [5]

    Bradshaw, B

    P. Bradshaw, B. Mohar, and L. Stacho. Bipartite graphs are(4 5 −ε) ∆ log ∆-choosable.arXiv preprint arXiv:2409.01513v1, 2024

    work page arXiv 2024

  6. [6]

    A. Char, K. Kawarabayashi, and L. Picasarri-Arrieta. Edge-colouring and orientations: applications to degree-boundedness andχ-boundedness.arXiv preprint arXiv:2506.23054, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  7. [7]

    P. Erdős. Problems and results in number theory and graph theory. InProceedings of the ninth Manitoba Conference on Numerical Mathematics and Computing, pages 3–21, 1979. 7

    work page 1979

  8. [8]

    Erdős, A

    P. Erdős, A. L. Rubin, and H. Taylor. Choosability in graphs.Congressus Numerantium, 26(4):125–157, 1979

    work page 1979

  9. [9]

    R. J. Kang. Improper choosability and Property B.J. Graph Theory, 73(3):342–353, 2013

    work page 2013

  10. [10]

    Kühn and D

    D. Kühn and D. Osthus. Induced subdivisions inKs,s-free graphs of large average degree. Combinatorica, 24(2):287–304, 2004

    work page 2004

  11. [11]

    Manber and M

    U. Manber and M. Tompa. The effect of number of hamiltonian paths on the complexity of a vertex-coloring problem.SIAM Journal on Computing, 13(1):109–115, 1984

    work page 1984

  12. [12]

    Mohar and H

    B. Mohar and H. Wu. Dichromatic number and fractional chromatic number.Forum of Mathematics, Sigma, 4:e32, 2016

    work page 2016

  13. [13]

    Neumann-Lara

    V. Neumann-Lara. The dichromatic number of a digraph.Journal of Combinatorial Theory, Series B, 33:265–270, 1982

    work page 1982

  14. [14]

    PhDthesis, UniversitéParisDauphine- PSL, to appear

    G.PuigiSurroca.Some topics on digraph colouring. PhDthesis, UniversitéParisDauphine- PSL, to appear

    work page

  15. [15]

    C. Rambaud. Personal communication, 2023

    work page 2023

  16. [16]

    Saxton and A

    D. Saxton and A. Thomason. Hypergraph containers.Inventiones mathematicae, 201:925– 992, 2015

    work page 2015

  17. [17]

    V. G. Vizing. Coloring the vertices of a graph in prescribed colors.Diskret. Analiz, 29(3):10, 1976. 8

    work page 1976