List edge-coloring

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 not3-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. ${\displaystyle \operatorname {ch} '(G)<2\chi '(G).}$
2. ${\displaystyle \operatorname {ch} '(K_{n,n})=n.}$ This is the Dinitz conjecture, proven by Galvin (1995).
3. ${\displaystyle \operatorname {ch} '(G)<(1+o(1))\chi '(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.

$${\displaystyle \operatorname {ch} '(G)=\chi '(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

• Galvin, Fred (1995), "The list chromatic index of a bipartite multigraph", Journal of Combinatorial Theory , Series B, 63: 153–158, doi: 10.1006/jctb.1995.1011 .
• Jensen, Tommy R.; Toft, Bjarne (1995), "12.20 List-Edge-Chromatic Numbers", Graph Coloring Problems, New York: Wiley-Interscience, pp. 201–202, ISBN   0-471-02865-7 .
• Kahn, Jeff (2000), "Asymptotics of the list chromatic index for multigraphs", Random Structures & Algorithms, 17 (2): 117–156, doi:10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9