Abstract
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 the Exponential Time Hypothesis (ETH) or other well established assumptions.
We notice that the same question can be asked for list edge coloring, a wellstudied 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 slowdown. 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.
BibTeX  Entry
@InProceedings{kowalik_et_al:LIPIcs:2018:8854,
author = {Lukasz Kowalik and Arkadiusz Socala},
title = {{Tight Lower Bounds for List Edge Coloring}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {28:128:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8854},
URN = {urn:nbn:de:0030drops88540},
doi = {10.4230/LIPIcs.SWAT.2018.28},
annote = {Keywords: list edge coloring, complexity, ETH lower bound}
}
Keywords: 

list edge coloring, complexity, ETH lower bound 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 