A linear-time algorithm for (1+ε)Δ-edge-coloring

We present a randomized algorithm that, given ε > 0, outputs a proper (1+ε)Δ-edge-coloring of an m-edge simple graph G of maximum degree Δ ≥ 1/ε in O(m\,log(1/ε)/ε⁴) time. For constant ε, this is the first linear-time algorithm for this problem without any restrictions on Δ other than the necessary bound Δ ≥ 1/ε. The best previous result in this direction, very recently obtained by Assadi, gives a randomized algorithm with expected running time O(m \, log(1/ε)) under the assumption Δ log n/ε; removing the lower bound on Δ was explicitly mentioned as a challenging open problem by Bhattacharya, Costa, Panski, and Solomon. Indeed, even for edge-coloring with 2Δ - 1 colors (i.e., meeting the "greedy" bound), no linear-time algorithm covering the full range of Δ has been known until now. Additionally, when ε = 1/Δ, our result yields an O(m\,Δ⁴log Δ)-time algorithm for (Δ+1)-edge-coloring, improving the bound O(m\, Δ¹⁷) from the authors' earlier work.