Paraphrasing Silvio's introduction to Leonid Levin, I'd say that this algorithmic problem deserves (i.e., requires) no introduction. [Sorry for repeating this joke.]
A key idea that appeared already in prior works is using an Eularian partition of the graph; that is, a partition of its edges to two sets such that in the corresponding subgraph each vertex has degree at most $d'=\ceil{d/2}+1$, where $d$ is the maximal degree in the original graph. Assuming first that all vertices have even degree, this partition can be found by finding an Eulerina cycle and assigning the edges along it in alternation.
(In case this cycle has odd length, you may get a single vertex of degree $(d/2)+1$ in one of the subgraphs. If the maximal degree was odd, then you can add dummy edges to make all degrees even, ending with degree at most $((d+1)/2)+1$ in each subgraph.)
The next idea, also used before, is to recurse: Find a $d'+1$-edge coloring of each of the two subgraphs and combine them getting a coloring in $d+O(1)$ colors. The idea is the uncolor $O(1)$ of the colors, and augment the resideual coloring that has $O(1)$ uncolored matching. The main contribution of the current work is performing this task efficiently (i.e., in complexity $O(m)$).
An afterthought (5-Feb-25): In the early 1980s, I was curious as to why we don't know of any (genuine) randomized graph algorithm (excluding UCONN...). As decades pass, more and more such algorithms were presented, and nowadays one would hardly have such a feeling. A frequent challenge is seeking de-randomization...
Vizing's Theorem from 1964 states that any n-vertex m-edge graph of maximum degree D can be edge colored using at most D+1 different colors. Vizing's original proof is algorithmic and implies that such an edge coloring can be found in O(mn) time. In this talk, I'll present a randomized algorithm that computes a (D+1)-edge coloring in near-linear time (in fact, in O(m log D) time, with high probability.
(Oded: I prefer the talk's abstract over the paper's...)
See arXiv 2410.05240.