, 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 proper list edge-coloring - one in which no two adjacent edges receive the same color - for every collection of lists of k colors.
The edge choosability
, or list edge colorability
, list edge chromatic number
, or list chromatic index
) of a graph G
is the least number k
such that G
Some properties of ch′(G):
- ch′(G) < 2 χ′(G).
- ch′(Kn,n) = n. (Galvin 1995)
- ch′(G) < (1 + o(1))χ′(G), i.e. the list chromatic index and the chromatic index agree asymptotically. (Kahn 2000)
Here χ′(G) is the chromatic index of G; and Kn,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.
- 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.
- Kahn, Jeff (2000). Asymptotics of the list chromatic index for multigraphs. Rand. Struct. Alg. 17, 117–156.