In mathematics, list edge-coloring is a type of graph coloring that combines

list coloring In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Tayl ...

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. 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 In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

Properties

Some properties of ch′(''G''): # ch′(''G'') < 2 χ′(''G''). # ch′(K_''n'',''n'') = ''n''. This is the

Dinitz conjecture In combinatorics, the Dinitz theorem (formerly known as Dinitz conjecture) is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin. The Dinitz theorem is that give ...

, proven by . # ch′(''G'') < (1 + o(1))χ′(''G''), i.e. the list chromatic index and the chromatic index agree asymptotically . Here χ′(''G'') is the

of ''G''; and K_''n'',''n'', the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...

with equal partite sets.

List coloring conjecture

The most famous open problem about list edge-coloring is probably the ''list coloring conjecture''. :ch′(''G'') = χ′(''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

s K_''n'',''n''.

References

* . * . * {{citation , doi = 10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9 , last1 = Kahn , first1 = Jeff , year = 2000 , title = Asymptotics of the list chromatic index for multigraphs , journal = Random Structures & Algorithms , volume = 17 , issue = 2, pages = 117–156 Graph coloring