List colorings of edge-critical graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph and set $\Delta=\max_{v\in V}\deg(v)$. A proper edge-coloring assigns different colors to any two edges sharing a vertex. Call $G$ edge-critical of maximum degree $\Delta$ when it has no proper edge-coloring using $\Delta$ colors, but $G-e$ has one for every edge $e\in E$. This fixes the criticality convention to deletion of a single edge.

For each edge $e$, prescribe a finite set $L(e)$ of allowed colors with $|L(e)|=\Delta$. Colors are abstract labels; the union of all the lists may contain more than $\Delta$ labels. Assume the lists are not all identical, meaning that $L(e)\ne L(f)$ for some edges $e,f$.

The conjecture says that every such list assignment admits a proper list edge-coloring: there is a map $c:E\to\bigcup_e L(e)$ satisfying $c(e)\in L(e)$ for every edge and $c(e)\ne c(f)$ for every pair of incident edges. The graph and all lists are quantified universally.

The exceptional case of identical lists must be excluded, because an identical list of $\Delta$ colors would contradict the defining obstruction of the critical graph. Nonidentical lists need not be disjoint, differ on every edge, or have any minimum amount of disagreement. The assertion is that even a small departure from one common list is sufficient, provided criticality holds for the underlying graph.

Short English statement

Does every nonconstant assignment of maximum-degree-sized edge lists color an edge-critical simple graph properly?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3200 (OPG-388), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, List colorings of edge-critical graphs. Original problem and discussion. http://www.openproblemgarden.org/op/list_colorings_of_edge_critical_graphs.