List edge-coloring

Encyclopedia : L : LI : LIS : 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 a 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. It is also 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 bipartite 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.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.