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).

Unsolved problem in mathematics

For every graph, is the list chromatic index equal to the chromatic index?

More unsolved problems in mathematics

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, ch'(G) 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 ch'(G):

1. ${\mathrm{ch}}^{\prime }(G)<2{\chi }^{\prime }(G).$
2. ${\mathrm{ch}}^{\prime }(K_{n,n})=n.$ This is the Dinitz conjecture, proven by .
3. ${\mathrm{ch}}^{\prime }(G)<(1+o(1)){\chi }^{\prime }(G),$ i.e. the list chromatic index and the chromatic index agree asymptotically .

Here χTemplate:Prime(G) 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.

$${\mathrm{ch}}^{\prime }(G)={\chi }^{\prime }(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 Template:Mvar.

References

• .
• .