ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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

χ⃗ℓ(G)=max⁡Dχ⃗ℓ(D),\vec\chi_{\ell}(G)=\max_D\vec\chi_{\ell}(D),

where the maximum is over all orientations DD of GG.

List 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_{\ell}(G)\geq f(k) implies χ⃗ℓ(G)≥k\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.