# co.combinatorics – Fastest algorithm to construct a proper edge \$(Delta(G)+1)\$-coloring of a simple graph

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)