The List Coloring Conjecture (LCC), open since the 1970s, asserts that every finite loopless multigraph GG satisfies χℓ′(G)=χ′(G)\chi'_\ell(G)=\chi'(G): whenever each edge receives its own palette of χ′(G)\chi'(G) colors, a proper edge coloring can be chosen from the palettes. Equivalently, every line graph is chromatic-choosable. Gordeev's 2019 preprint reproved the LCC for line-perfect multigraphs — a class result due to Peterson and Woodall (1999), independently rediscovered by Gordeev — while the general case remains open. Since the line-perfect case is settled, every unsettled instance must have an imperfect line graph, although some imperfect-line-graph families (such as odd-order complete graphs) are themselves settled; the conjecture remains open, with current progress proceeding family by family (most recently two new infinite families of even-order complete graphs, in an August 2026 preprint).

Background

An edge coloring of a multigraph assigns colors to its edges so that edges sharing a vertex receive different colors; the minimum number of colors needed is the chromatic index χ′(G)\chi'(G). A classical edge-coloring theorem bounds the chromatic index of a simple graph of maximum degree Δ\Delta by Δ\Delta or Δ+1\Delta+1 (graphs meeting the lower bound are called class 1, the others class 2), while parallel edges can force larger values. Edge coloring a graph GG is equivalent to vertex-coloring its line graph L(G)L(G), the graph whose vertices are the edges of GG, two being adjacent when the corresponding edges of GG share an endpoint; thus χ′(G)=χ(L(G))\chi'(G)=\chi(L(G)).

In list coloring, each vertex vv of a graph HH comes with its own palette AvA_v of admissible colors, and one must produce a proper coloring in which every vertex takes its color from its own palette. The least kk such that this is always possible when all palettes have size kk is the choice number (list chromatic number) χℓ(H)\chi_\ell(H). Trivially χℓ(H)≥χ(H)\chi_\ell(H)\ge\chi(H), and the inequality can be strict even for bipartite graphs. Applying these definitions to line graphs yields the list chromatic index χℓ′(G)\chi'_\ell(G): the least kk such that, whenever each edge ee of GG receives a palette AeA_e of kk colors, a proper edge coloring can be chosen from the palettes. Again χℓ′(G)≥χ′(G)\chi'_\ell(G)\ge\chi'(G) always.

The List Coloring Conjecture (LCC), also called the List Edge Coloring Conjecture, asserts that for line graphs this trivial inequality is always tight:

χℓ′(G)=χ′(G) for every finite loopless multigraph G,\chi'_\ell(G)=\chi'(G)\ \text{for every finite loopless multigraph}\ G,

equivalently, every line graph is chromatic-choosable, i.e. χℓ(H)=χ(H)\chi_\ell(H)=\chi(H) for every line graph HH. The conjecture took shape in the 1970s–80s; see the historical account of Häggkvist and Chetwynd [5, p. 509]. Standard references attribute it independently to several authors. It has become one of the central open problems of graph coloring.

The strongest general results to date use two different techniques. Galvin (1995) proved the LCC for every bipartite multigraph — the kernel method: a kernel of a digraph is an independent set KK of vertices such that every vertex outside KK sends an arc to KK, and an orientation of a graph whose every induced subdigraph has a kernel, with outdegrees below the palette sizes, forces choosability; Galvin combined this with Maffray's theorem (1992) that a line graph is perfect exactly when every normal orientation of it has a kernel — an orientation being normal when every clique (a set of pairwise adjacent vertices) contains a sink, a vertex to which every other vertex of the clique points. Kahn (1996), by the entropy method, proved the asymptotic form χℓ′(G)=(1+o(1))χ′(G)\chi'_\ell(G)=(1+o(1))\chi'(G) for every multigraph.

A multigraph is called line-perfect when its line graph is perfect — a graph being perfect if every induced subgraph has chromatic number equal to its clique number (the size of a largest set of pairwise adjacent vertices). Line-perfect multigraphs are exactly those whose every block (maximal subgraph with no cut vertex) is bipartite, a K4K_4 with arbitrary edge multiplicities, or a K1,1,nK_{1,1,n} (nn triangles sharing one common edge, multiple edges allowed). Peterson and Woodall (1999; erratum 2003), and independently Gordeev (2019), proved the LCC for all line-perfect multigraphs, extending Galvin's theorem beyond the bipartite case: Gordeev's proof runs Galvin's kernel/orientation argument on bipartite blocks and bespoke inductive Hall-type transversal arguments on K4K_4-type and K1,1,nK_{1,1,n}-type blocks. Since this settles exactly the multigraphs with perfect line graphs, every surviving open instance must have an imperfect line graph — one containing odd cycles of length at least 5 or other obstructions — for example even-order complete graphs, snarks (bridgeless cubic, i.e. 3-regular, graphs that are not 3-edge-colorable), and class-2 multigraphs generally. Other settled families include complete graphs of odd order, via χℓ′(Kn)≤n\chi'_\ell(K_n)\le n (Häggkvist and Janssen 1997); complete graphs of prime degree (Schauz 2014); certain 1-factorable multigraphs — those whose edge set partitions into perfect matchings, each covering every vertex exactly once — including the regular planar class-1 ones (Ellingham and Goddyn 1996); and simple graphs whose odd cycles pairwise intersect in at most one edge (McDonald and Puleo 2018), a strict extension beyond line-perfect graphs.

Problem Statement

Prove or refute the List Coloring Conjecture: for every finite loopless multigraph GG,

χℓ′(G)=χ′(G).\chi'_\ell(G)=\chi'(G).

That is, prove that for every multigraph GG and every assignment of color lists AeA_e with ∣Ae∣=χ′(G)|A_e|=\chi'(G) to the edges ee of GG, there exists a proper edge coloring of GG in which each edge receives a color from its own list — the inequality χℓ′(G)≥χ′(G)\chi'_\ell(G)\ge\chi'(G) being trivial, the conjecture is the converse bound χℓ′(G)≤χ′(G)\chi'_\ell(G)\le\chi'(G). Equivalently: is every line graph chromatic-choosable, χℓ(L(G))=χ(L(G))\chi_\ell(L(G))=\chi(L(G)) for every multigraph GG? Since multigraphs whose line graph is perfect are settled (Peterson and Woodall 1999; independently reproved by Gordeev 2019), any open instance must have an imperfect line graph; the unsettled cases include even-order complete graphs beyond the arithmetic families settled to date and class-2 multigraphs in general. A resolution must be unconditional and unrestricted in the multigraph class; a refutation consists of a single concrete multigraph GG together with an assignment of lists of size χ′(G)\chi'(G) per edge from which no proper coloring exists.

References

  1. Alexey Gordeev. Proof of the List Coloring Conjecture for line perfect multigraphs. arXiv preprint, 2019. DOI 10.48550/arXiv.1904.06662. https://arxiv.org/abs/1904.06662
  2. Dale Peterson and Douglas R. Woodall. Edge-choosability in line-perfect multigraphs. Discrete Mathematics 202 (1999) 191-199. DOI 10.1016/S0012-365X(98)00293-3. https://doi.org/10.1016/S0012-365X(98)00293-3
  3. Dale Peterson and Douglas R. Woodall. Erratum to 'Edge-choosability in line-perfect multigraphs' [Discrete Mathematics 202 (1999) 191]. Discrete Mathematics 260 (2003) 323-326. DOI 10.1016/S0012-365X(02)00676-3. https://doi.org/10.1016/S0012-365X(02)00676-3
  4. Fred Galvin. The list chromatic index of a bipartite multigraph. Journal of Combinatorial Theory, Series B 63 (1995) 153-158. DOI 10.1006/jctb.1995.1011. https://doi.org/10.1006/jctb.1995.1011
  5. Roland Häggkvist and Amanda Chetwynd. Some upper bounds on the total and list chromatic numbers of multigraphs. Journal of Graph Theory 16 (1992) 503-516. DOI 10.1002/jgt.3190160510. https://doi.org/10.1002/jgt.3190160510
  6. Roland Häggkvist and Jeannette Janssen. New bounds on the list-chromatic index of the complete graph and other simple graphs. Combinatorics, Probability and Computing 6 (1997) 295-313. DOI 10.1017/S0963548397002927. https://doi.org/10.1017/S0963548397002927
  7. Frédéric Maffray. Kernels in perfect line-graphs. Journal of Combinatorial Theory, Series B 55 (1992) 1-8. DOI 10.1016/0095-8956(92)90028-V. https://doi.org/10.1016/0095-8956(92)90028-V
  8. Jeff Kahn. Asymptotically good list-colorings. Journal of Combinatorial Theory, Series A 73 (1996) 1-59. DOI 10.1006/jcta.1996.0001. https://doi.org/10.1006/jcta.1996.0001
  9. M. N. Ellingham and Luis Goddyn. List edge colourings of some 1-factorable multigraphs. Combinatorica 16 (1996) 343-352. DOI 10.1007/BF01261320. https://doi.org/10.1007/BF01261320
  10. Uwe Schauz. Proof of the List Edge Coloring Conjecture for Complete Graphs of Prime Degree. The Electronic Journal of Combinatorics 21(3) (2014). DOI 10.37236/4084. https://doi.org/10.37236/4084
  11. Jessica McDonald and Gregory J. Puleo. The list chromatic index of simple graphs whose odd cycles intersect in at most one edge. Discrete Mathematics 341 (2018) 713-722. DOI 10.1016/j.disc.2017.11.012. https://doi.org/10.1016/j.disc.2017.11.012 (preprint: arXiv:1507.05933, https://arxiv.org/abs/1507.05933)
  12. Jessica McDonald. A list analog of Vizing's Theorem for simple graphs with triangles but no other odd cycles. arXiv preprint, 2014, withdrawn by the author. arXiv:1407.0626. https://arxiv.org/abs/1407.0626
  13. Nandana K. Vasudevan, K. Somasundaram, and N. Narayanan. List-Coloring and Chromatic-Choosability - A Dynamic Survey. arXiv preprint, 2026. DOI 10.48550/arXiv.2606.31702. https://arxiv.org/abs/2606.31702
  14. Amir Jafari. The List Edge-Coloring Conjecture for Two New Infinite Families of Complete Graphs. arXiv preprint, 2026. DOI 10.48550/arXiv.2608.22895. https://arxiv.org/abs/2608.22895
  15. Uwe Schauz. Orientations of 1-Factorizations and the List Chromatic Index of Small Graphs. arXiv preprint, 2017. arXiv:1705.00484. https://arxiv.org/abs/1705.00484