List edge-coloring

File:List-edge coloring (cb).svg

This assignment of lists, each with length k = 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 G is k-edge-choosable if every instance of list edge-coloring that has G as its underlying graph and that provides at least k allowed colors for each edge of G has a proper coloring. In other words, when the list for each edge has length k, no matter which colors are put in each list, a color can be selected from each list so that G is properly colored. The edge choosability, or list edge colorability, list edge chromatic number, or list chromatic index, ch'(G) of graph G is the least number k such that G is k-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 Galvin (1995).
3. ${\mathrm{ch}}^{\prime }(G)<(1+o(1)){\chi }^{\prime }(G),$ i.e. the list chromatic index and the chromatic index agree asymptotically (Kahn 2000).

Here χ′(G) is the chromatic index of G; and K_n,n, 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; Jensen & Toft (1995) overview its history. The Dinitz conjecture, proven by Galvin (1995), is the special case of the list coloring conjecture for the complete bipartite graphs K_n,n.

References

• .
• .