List edge-colouring with no extra colours
Let $G$ be a finite loopless multigraph with at least one edge (parallel edges allowed), and let $\chi'(G)$ be its chromatic index. Its list chromatic index $\chi'_\ell(G)$ is the least $k$ such that, whenever every edge $e$ is given a finite list $L(e)$ of at least $k$ colours, $G$ has a proper edge-colouring $c$ with $c(e) \in L(e)$ for every edge $e$. Identical lists show $\chi'_\ell(G) \ge \chi'(G)$.
Galvin proved $\chi'_\ell(G) = \chi'(G)$ for bipartite multigraphs. Häggkvist and Janssen proved $\chi'_\ell(K_n) \le n$, which gives equality for complete graphs of odd order, and Schauz proved $\chi'_\ell(K_{p+1}) = p$ for every odd prime $p$. Kahn proved that $\chi'_\ell(G) / \chi'^*(G) \to 1$ as $\chi'^*(G) \to \infty$, where $\chi'^*$ is the fractional chromatic index; since $\chi'^* \le \chi' \le \chi'_\ell$, the list chromatic index and the chromatic index agree asymptotically.
Problem. Is $\chi'_\ell(G) = \chi'(G)$ for every finite loopless multigraph $G$, that is, does every assignment of lists with $|L(e)| \ge \chi'(G)$ for all edges $e$ admit a proper edge-colouring from the lists?
Source: The List Colouring Conjecture, proposed independently by several researchers, seemingly first by Vizing (1975); see Jensen and Toft (1995), §12.20, and Kahn (2000). For multigraphs as stated by Schauz (2014), Conjecture 1.1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, edge colourings, list colourings, multigraphs
References
@book{jensen1995,
author = {Jensen, Tommy R. and Toft, Bjarne},
title = {Graph Coloring Problems},
series = {Wiley-Interscience Series in Discrete Mathematics and Optimization},
publisher = {John Wiley \& Sons},
address = {New York},
year = {1995},
doi = {10.1002/9781118032497},
}
@article{schauz2014,
author = {Schauz, Uwe},
title = {Proof of the list edge coloring conjecture for complete graphs of prime degree},
journal = {Electron. J. Combin.},
volume = {21},
number = {3},
year = {2014},
pages = {P3.43},
doi = {10.37236/4084},
}
@article{kahn2000,
author = {Kahn, Jeff},
title = {Asymptotics of the list-chromatic index for multigraphs},
journal = {Random Structures Algorithms},
volume = {17},
number = {2},
year = {2000},
pages = {117--156},
doi = {10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9},
}
@article{galvin1995,
author = {Galvin, Fred},
title = {The list chromatic index of a bipartite multigraph},
journal = {J. Combin. Theory Ser. B},
volume = {63},
number = {1},
year = {1995},
pages = {153--158},
doi = {10.1006/jctb.1995.1011},
}
@article{haggkvist1997,
author = {H{\"a}ggkvist, Roland and Janssen, Jeannette},
title = {New bounds on the list-chromatic index of the complete graph and other simple graphs},
journal = {Combin. Probab. Comput.},
volume = {6},
number = {3},
year = {1997},
pages = {295--313},
doi = {10.1017/S0963548397002927},
}
@misc{aim-list-edge-colouring,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{List edge-colouring with no extra colours}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/333-list-edge-colouring.md},
note = {Entry 333 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00451, "List edge-colouring with no extra colours", clopen.solutions.