Misra & Gries edge-coloring algorithm

Summary

The Misra & Gries edge-coloring algorithm is a polynomial-time algorithm in graph theory that finds an edge coloring of any simple graph. The coloring produced uses at most $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph. This is optimal for some graphs, and it uses at most one color more than optimal for all others. The existence of such a coloring is guaranteed by Vizing's theorem.