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 is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest (a graph in which each vertex has at most one outgoing edge) on the neighbors of : for each neighbor of , the algorithm finds a color that is not used by any of the edges incident to , finds the vertex (if it exists) for which edge has color , and adds as an edge to . There are two cases: If the pseudoforest constructed in this way contains a path from to a vertex that has no outgoing edges in , then there is a color that is available both at and . Recoloring edge with color allows the remaining edge colors to be shifted one step along this path: for each vertex in the path, edge takes the color that was previously used by the successor of in the path. This leads to a new coloring that includes edge . If, on the other hand, the path starting from in the pseudoforest leads to a cycle, let be the neighbor of at which the path joins the cycle, let be the color of edge , and let be a color that is not used by any of the edges at vertex . Then swapping colors and on a Kempe chain either breaks the cycle or the edge on which the path joins the cycle, leading to the previous case. With some simple data structures to keep track of the colors that are used and available at each vertex, the construction of and the recoloring steps of the algorithm can all be implemented in time , where is the number of vertices in the input graph. Since these steps need to be repeated times, with each repetition increasing the number of colored edges by one, the total time is . In an unpublished technical report, claimed a faster time bound for the same problem of coloring with colors.