List Edge-coloring

In graph theory, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring.
An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color.

A graph is -edge-choosable if every instance of list edge-coloring that has as its underlying graph and that provides at least allowed colors for each edge of has a proper coloring. In other words, when the list for each edge has length , no matter which colors are put in each list, a color can be selected from each list so that is properly colored.
The edge choosability, or ''list edge colorability'', ''list edge chromatic number'', or ''list chromatic index'', of graph is the least number such that is -edge-choosable. It is conjectured that it always equals the chromatic index.

Properties

Some properties of :
# $\operatorname'(G) < 2 \chi'(G).$
# $\operatorname'(K_) = n.$ This is the Dinitz conjecture, proven by .
# $\operatorname'(G) < (1 + o(1)) \chi'(G),$ i.e. the list chromatic index and the chromatic index agree asymptotically .
Here is the chromatic index of ; and , the complete bipartite graph with equal partite sets.

List coloring conjecture

The most famous open problem about list edge-coloring is probably the ''list coloring conjecture''.

$\operatorname'(G) = \chi'(G).$

This conjecture has a fuzzy origin; overview its history. The Dinitz conjecture, proven by , is the special case of the list coloring conjecture for the complete bipartite graphs .

References

* .
* .
* {{citation , doi = 10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9 , last1 = Kahn , first1 = Jeff , year = 2000 , title = Asymptotics of the list chromatic index for multigraphs , journal = Random Structures & Algorithms , volume = 17 , issue = 2, pages = 117–156

Graph coloring