List Coloring Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite undirected loopless multigraph; parallel edges are allowed. Two different edges are adjacent when they share an endpoint. A proper edge coloring assigns colors to edges so that adjacent edges have different colors. The chromatic index $\chi'(G)$ is the smallest number of colors allowing such a coloring. For a choice of finite color lists $L(e)$, a proper list edge coloring must additionally assign to each edge a color from its own list. The list chromatic index $\chi'_{\ell}(G)$ is the least nonnegative integer $k$ such that every assignment of lists with $|L(e)|\ge k$ has a proper list edge coloring. Both indices are zero when $E$ is empty.

Statement recorded in the supplied source.

For every finite loopless multigraph $G$, is \[ \chi'_{\ell}(G)=\chi'(G)? \] Equivalently, is a proper edge coloring always possible when each edge is given an arbitrary list of $\chi'(G)$ colors? The statement concerns every graph, including non-bipartite graphs. [S2]

Short English statement

Does allowing a different list of permitted colors on each edge ever require more colors than ordinary proper edge coloring?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1399 (GRAPH-012). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Fotis Iliopoulos and Alistair Sinclair, Efficiently List-Edge Coloring Multigraphs Asymptotically Optimally, arXiv:1812.10309v3 (2021), Section 1, list chromatic index and List Coloring Conjecture preceding Theorem 1.2. https://arxiv.org/pdf/1812.10309v3.