# Edge list coloring conjecture

 Importance: High ✭✭✭
 Author(s):
 Subject: Graph Theory » Coloring » » Edge coloring
 Keywords:
 Posted by: tchow on: September 25th, 2008
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.