List edge-coloring explained

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.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{ch}'(G) < 2 \chi'(G). \operatorname{ch}'(K _{n,n} ) = n. This is the Dinitz conjecture, proven by .\operatorname{ch}'(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.

$$\backslash operatorname\text{'}(G)\; =\; \backslash chi\text{'}(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

• .
• .