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\, (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 \, (1/) ) under the assumption 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\, ⁴) -time algorithm for (+1) -edge-coloring, improving the bound O (m\, ^17) from the authors' earlier work.