List edge-coloring conjecture

Two links sharing an endpoint need different colors. Suppose one may use red or blue and the other red or green: choosing blue and red works. A shared two-color palette also suffices for this little graph. If every edge of any finite loopless multigraph has its own list as long as the smallest shared palette needed for that graph, must a valid choice always exist? Parallel edges are allowed, and all lists of that length are included.[1]

Can separate availability lists force more choices per edge than the conflicts require under a common palette? A two-edge path has ordinary chromatic index two. With lists {red, blue} and {red, green}, blue on the first edge and red on the second is valid; every pair of lists containing two distinct colors also permits different choices.

For a finite loopless multigraph $G$, $\chi^{\prime}(G)$ is the minimum ordinary edge-coloring count. The list chromatic index $\chi^{\prime}_{\ell}(G)$ is the least $k$ such that every assignment of $k$ allowed colors to each edge has a proper coloring from those lists. Must $\chi^{\prime}_{\ell}(G)=\chi^{\prime}(G)$? The lists are arbitrary; parallel edges are permitted, loops excluded.[1] [2]

Exact equality is known for bipartite multigraphs. The revised 2026 preprint reports additional complete-graph families, while the constructive general result is asymptotic and allows extra list length. These do not settle exact equality for every loopless multigraph.[1] [2]

Constructive asymptotic optimality and the new family-specific claims do not establish the exact all-graph list bound.[1] [2]

A link can model a transfer between two endpoints, and a color a time slot; links sharing an endpoint cannot use the same slot. Different allowed slots turn a shared-calendar problem into a list problem. This distinguishes conflicts caused by shared endpoints from constraints caused by local availability. The analogy specifies an abstract allocation model, not a promised improvement in real network performance.[1]

Each color class in an ordinary edge coloring is a matching, a collection of edges that do not share endpoints. Lists restrict which such classes an individual edge may join, so the problem adds local availability to a global matching decomposition. Asymptotic methods control this interaction while allowing a small relative surplus of choices. Exact equality asks whether that surplus reflects a real obstruction or a limitation of those methods, without claiming an exact efficient algorithm.[1] [2]