If Edge Coloring is Hard under SETH, then SETH is False

Alexander S. Kulikov, Ivan Mihajlin

The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time $2^{o(n^2)}$ (let alone $2^{O(n)}$), where $n$ is the number of nodes of the inp…