linguistic:translation
Algorithms

Misra & Gries (1992) describe a polynomial time algorithm for coloring the edges of any graph with Δ + 1 colors, where Δ is the maximum degree of the graph. That is, the algorithm uses the optimal number of colors for graphs of class two, and uses at most one more color than necessary for all graphs. Their algorithm follows the same strategy as Vizing's original proof of his theorem: it starts with an uncolored graph, and then repeatedly finds a way of recoloring the graph in order to increase the number of colored edges by one.

More specifically, suppose that uv is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest P (a graph in which each vertex has at most one outgoing edge) on the neighbors of u: for each neighbor p of u, the algorithm finds a color c that is not used by any of the edges incident to p, finds the vertex q (if it exists) for which edge uq has color c, and adds pq as an edge to P. There are two cases:

With some simple data structures to keep track of the colors that are used and available at each vertex, the construction of P and the recoloring steps of the algorithm can all be implemented in time O(n), where n is the number of vertices in the input graph. Since these steps need to be repeated m times, with each repetition increasing the number of colored edges by one, the total time is O(mn).

In an unpublished technical report, Gabow et al. (1985) claimed a faster O (m n log n) {\displaystyle O(m{\sqrt {n}}\log n)} time bound for the same problem of coloring with Δ + 1 colors.