In mathematics, **list edge-coloring** is a type of graph coloring. More precisely, a list edge-coloring is a *choice function* that maps every edge to a color from a prescribed list for that edge. A graph is *k*-edge-choosable if it has an list edge-coloring for every collection of lists of k colors. The **edge choosability**, or *list edge colorability*, *list edge chromatic number*, or *list chromatic index*, ch′(*G*) of a graph *G* is the least number *k* such that *G* is *k*-edge-choosable. Some properties of ch′(*G*): - ch′(
*G*) < 2 χ′(*G*). - ch′(K
_{n,n}) = *n*. (Galvin 1995) Here χ′(*G*) is the chromatic index of *G*; and K_{n,n}, the complete bipartite graph with equal partite sets. The most famous open problem about list edge-coloring is probably the *list coloring conjecture*.
**List coloring conjecture.** - ch′(
*G*) = χ′(*G*). This conjecture has a fuzzy origin. Interested readers are directed to [Jensen, Toft 1995] for an overview of its history. This conjecture is a generalization of the longstanding Dinitz conjecture, which was eventually solved by Galvin in 1995 using list edge-coloring.
## References - Galvin, Fred (1995). The list chromatic index of a bipartitle multigraph.
*J. Combin. Theory (B)* **63**, 153–158. - Jensen, Tommy R.; Toft, Bjarne (1995).
*Graph coloring problems*. New York: Wiley-Interscience. ISBN 0-471-02865-7. |