Math Conjectures

List Edge-Coloring Conjecture

OPENMajorConjectureProposed c. 1975 · Standard version

Canonical statement

For every finite loopless multigraph GG,
χℓ′(G)=χ′(G), \chi'_{\ell}(G)=\chi'(G),
where χ′(G)\chi'(G) is its edge-chromatic number and χℓ′(G)\chi'_{\ell}(G) is the least kk such that, whenever every edge ee is assigned a list L(e)L(e) of at least kk colors, a proper edge coloring c(e)∈L(e)c(e)\in L(e) exists.
View source LaTeX
For every finite loopless multigraph \(G\),
\[
  \chi'_{\ell}(G)=\chi'(G),
\]
where \(\chi'(G)\) is its edge-chromatic number and
\(\chi'_{\ell}(G)\) is the least \(k\) such that, whenever every edge
\(e\) is assigned a list \(L(e)\) of at least \(k\) colors, a proper edge
coloring \(c(e)\in L(e)\) exists.
GRAPH-007:[Vizing1976List][Galvin1995ListEdge][Kahn1996AsymptoticList]
Graph theoryCombinatorics

Notes

The list edge-coloring conjecture concerns edge colorings in which each edge ee must receive a color from its own prescribed list L(e)L(e). Writing χ′(G)\chi'(G) for the ordinary edge-chromatic number and χℓ′(G)\chi'_{\ell}(G) for the least kk such that lists of size kk always admit a proper edge coloring, the conjecture asserts that χℓ′(G)=χ′(G)\chi'_{\ell}(G)=\chi'(G) for every finite loopless multigraph — arbitrary lists should be no harder than a common palette. The formulation crystallized around the mid-1970s in the early literature on list colorings, to which Vizing was a central contributor [Vizing1976List]; no single first statement is documented.

The outstanding positive result is Galvin's theorem that equality holds for every bipartite multigraph [Galvin1995ListEdge], which in particular settled the Dinitz problem. Kahn proved the conjecture asymptotically: χℓ′(G)=(1+o(1))χ′(G)\chi'_{\ell}(G)=(1+o(1))\chi'(G) as the maximum degree grows [Kahn1996AsymptoticList].

A resolution must bridge the gap between the bipartite and asymptotic results and the full conjecture; for general loopless multigraphs the exact equality remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.