A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing’s theorem states that every simple graph $G$ has a proper edge coloring using at most maximum degree plus one colors. In (1), the authors showed that there is an $O(mn)$-time algorithm to construct a proper edge $(Delta(G)+1)$-coloring of a simple graph whth $m$ edges and $n$ vertices. I wonder whether there is a faster algorithm to construct such an edge coloring.
(1) J. Misra, and D. Gries. A constructive proof of Vizing’s theorem.Inform. Process. Lett.41(3)131–133 (1992)