List edge-coloring

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):

1. ch′(G) < 2 χ′(G).
2. 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.