  The fastest algorithms for edge coloring run in time $2^m n^{O(1)}$, where
$m$ and $n$ are the number of edges and vertices of the input graph,
respectively. For dense graphs, this bound becomes $2^{\Theta(n^2)}$. This is a
somewhat unique situation, since most of the studied graph problems admit
algorithms running in time $2^{O(n\log n)}$. It is a notorious open problem to
either show an algorithm for edge coloring running in time $2^{o(n^2)}$ or to
refute it, assuming Exponential Time Hypothesis (ETH) or other well established
assumption.
  We notice that the same question can be asked for list edge coloring, a
well-studied generalization of edge coloring where every edge comes with a set
(often called a list) of allowed colors. Our main result states that list edge
coloring for simple graphs does not admit an algorithm running in time
$2^{o(n^2)}$, unless ETH fails. Interestingly, the algorithm for edge coloring
running in time $2^m n^{O(1)}$ generalizes to the list version without any
asymptotic slow-down. Thus, our lower bound is essentially tight. This also
means that in order to design an algorithm running in time $2^{o(n^2)}$ for
edge coloring, one has to exploit its special features compared to the list
version.

Data Structures and Algorithms