# Edge list coloring conjecture

**Conjecture**Let be a loopless multigraph. Then the edge chromatic number of equals the list edge chromatic number of .

The list edge chromatic number of is also known as the *list chromatic index*, the *edge choosability*, or the *edge choice number* of . It is the list chromatic number of the line graph of . Similarly, the edge chromatic number of is also known as the *edge chromatic index*, and it is the chromatic number of the line graph of . The chromatic number of a graph is always less than or equal to the list chromatic number; the two quantities differ in general, but the conjecture says that they coincide for line graphs. Sometime the conjecture is simply referred to as the *list coloring conjecture*, although this is perhaps poor terminology since there exist other conjectures about list coloring.

Perhaps the most famous partial result is Galvin's theorem [G] that the conjecture holds for bipartite multigraphs. Galvin's result settled the well-known *Dinitz conjecture* in the affirmative.

The conjecture has been attributed to many different people. See [JT, Problem 12.20] for a history of the problem up to 1995.

## Bibliography

[G] Fred Galvin, The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B 63 (1995), 153–158.

[JT] Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems. New York: Wiley-Interscience, 1995.

* indicates original appearance(s) of problem.