Open Problem Garden

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.