View source for List edge-coloring

{{short description|Graph edge coloring with a limited number of allowed colors}}
[[File:List-edge coloring (cb).svg|thumb|270px|This assignment of lists, each with length {{mvar|k}} = 3, makes it so that no matter which colors are chosen from each list for the edge's color, the graph cannot be [[edge coloring|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|mathematics|For every graph, is the list chromatic index equal to the chromatic index?}}

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

==Properties==
Some properties of {{math|ch'(''G'')}}:
# <math>\operatorname{ch}'(G) < 2 \chi'(G).</math>
# <math>\operatorname{ch}'(K_{n,n}) = n.</math>  This is the [[Dinitz conjecture]], proven by {{harvtxt|Galvin|1995}}.
# <math>\operatorname{ch}'(G) < (1 + o(1)) \chi'(G),</math> i.e. the list chromatic index and the chromatic index agree asymptotically {{harv|Kahn|2000}}.
Here {{math|''χ''{{prime}}(''G'')}} is the [[Edge coloring|chromatic index]] of {{mvar|G}}; and {{mvar|K{{sub|n,n}}}}, the [[complete bipartite graph]] with equal [[Glossary of graph theory|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; {{harvtxt|Jensen|Toft|1995}} overview its history. The Dinitz conjecture, proven by {{harvtxt|Galvin|1995}}, is the special case of the list coloring conjecture for the [[complete bipartite graph]]s {{mvar|K<sub>n,n</sub>}}.

== References ==

* {{citation | doi = 10.1006/jctb.1995.1011 | last1 = Galvin | first1 = Fred | author-link = Fred Galvin | year = 1995 | title = The list chromatic index of a bipartite multigraph | journal = [[Journal of Combinatorial Theory]] | series = Series B | volume = 63 | pages = 153–158 | doi-access = free }}.
* {{citation|last1=Jensen|first1=Tommy R.|last2=Toft|first2=Bjarne|year=1995|title=Graph Coloring Problems|location=New York|publisher=Wiley-Interscience|isbn=0-471-02865-7|chapter=12.20 List-Edge-Chromatic Numbers|pages=201–202}}.
* {{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 }}

[[Category:Graph coloring]]