List edge-coloring

File:List-edge coloring (cb).svg

This assignment of lists, each with length Template:Mvar = 3, makes it so that no matter which colors are chosen from each list for the edge's color, the graph cannot be properly colored. The graph is therefore not 3-edge-choosable, and has a list chromatic index of at least 4 (in this case, it is 4).

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

Properties

Some properties of Template:Math:

1. <math>\operatorname{ch}'(G) < 2 \chi'(G).</math>
2. <math>\operatorname{ch}'(K_{n,n}) = n.</math> This is the Dinitz conjecture, proven by Template:Harvtxt.
3. <math>\operatorname{ch}'(G) < (1 + o(1)) \chi'(G),</math> i.e. the list chromatic index and the chromatic index agree asymptotically Template:Harv.

Here Template:Math is the chromatic index of Template:Mvar; and Template:Mvar, 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.

<math display=block>\operatorname{ch}'(G) = \chi'(G).</math>

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

References

• Template:Citation.
• Template:Citation.
• Template:Citation