Algorithm in graph theory
The Misra &amp; 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 formula_1 colors, where formula_2 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.
It was first published by Jayadev Misra and David Gries in 1992. It is a simplification of a prior algorithm by Béla Bollobás.
This algorithm is the fastest known almost-optimal algorithm for edge coloring, executing in formula_3 time. A faster time bound of formula_4 was claimed in a 1985 technical report by Gabow et al., but this has never been published.
In general, optimal edge coloring is NP-complete, so it is very unlikely that a polynomial time algorithm exists. There are however exponential time exact edge coloring algorithms that give an optimal solution.
Key concepts.
Free color.
A color "c" is said to be free on a vertex "u" if no incident edge of "u" has color "c".
Fan.
A fan of a vertex "X" is a sequence of vertices "F"[1:"k"] that satisfies the following conditions:
Given a fan "F", any edge ("X","F"["i"]) for 1 ≤ "i" ≤ "k" is a fan edge.
Rotating a fan.
Given a fan "F"[1:"k"] of a vertex "X", the "rotate fan" operation does the following: for "i" = 1, ..., "k"-1, assign the color of ("X","F"["i" + 1]) to edge ("X","F"["i"]).
Finally, uncolor ("X", "F"["k"]).
This operation leaves the coloring valid because, by the definition of a fan, the color of ("X","F"["i"+1]) was free on "F"["i"].
cd-path.
Let "c" and "d" be colors.
A "cd""X"-path is an edge path that goes through vertex "X", only contains edges colored "c" or "d" and is maximal.
If neither "c" nor "d" is incident on "X", there is no such path.
If such a path exists, it is unique as at most one edge of each color can be incident on "X".
Inverting a cd-path.
The operation "invert the "cd""X"-path" switches every edge on the path colored "c" to "d" and every edge colored "d" to "c".
Inverting a path can be useful to free a color on "X" if "X" is one of the endpoints of the path: if color "c" but not "d" was incident on "X", now color "d" but not "c" is incident on "X", freeing "c" for "X".
This operation leaves the coloring valid.
For vertices on the path that are not endpoints, no new color is added.
For endpoints, the operation switches the color of one of its edges between "c" and "d".
This is valid: suppose the endpoint was connected by a "c" edge, then "d" was free on this endpoint because otherwise, this vertex cannot be an endpoint.
Since "d" was free, this edge can switch to "d".
Algorithm.
 algorithm Misra &amp; Gries edge coloring algorithm is
 input: A graph G.
 output: A proper coloring c of the edges of G.
 Let U := E(G)
 while U ≠ ∅ do
 Let (X,v) be any edge in U. 
 Let F[1:k] be a maximal fan of X with F[1]=v.
 Let c be a free color on X and d be a free color on F[k]. 
 Invert the cdX-path. 
 Let w ∈ {1..k} such that F'=F[1:w] is a fan and d is free on F[w]. 
 Rotate F'.
 Set the color of (X,w) to d.
 end while
Proof of correctness.
The correctness of the algorithm is proved in three parts.
First, it is shown that the inversion of the "cd""X"-path guarantees a "w" ∈ {1..,"k"} such that "F"′ = "F"[1:"w"] is a fan and "d" is free on "F"["w"].
Then, it is shown that the edge coloring is valid and requires at most Δ+1 colors.
Path inversion guarantee.
Prior to the inversion, there are two cases:
Case 1: the fan has no edge colored "d".
Since "F" is a maximal fan on "X" and "d" is free on "F"["k"], "d" is free on "X".
Otherwise, suppose an edge ("X","u") has color "d", then "u" can be added to "F" to make a bigger fan, contradicting with "F" being maximal.
Thus, "d" is free on "X", and since "c" is also free on "X", there is no "cd""X"-path and the inversion has no effect on the graph.
Set "w" = "k".
Case 2: the fan has one edge with color "d".
Let ("X","F"["i"+1]) be this edge.
Note that "i"+1 ≠ 1 since ("X","F"[1]) is uncolored.
By definition of a fan, "d" is free on "F"["i"].
Also, "i" ≠ "k" since the fan has length "k" but there exists a "F"["i"+1].
We can now show that after the inversion, 
 (1): for "j" ∈ {1, ..., "k"-1} \ {"i"}, the color of ("X","F"["j"+1]) is free on "F"["j"].
Note that prior to the inversion, "c" is free on "X" and ("X","F"["i"+1]) has color "d", so the other edges in the fan, i.e., all ("X","F"["j"+1]) above, cannot have color "c" or "d".
Since the inversion only affects edges that are colored "c" or "d", (1) holds.
Case2.1: "F"["i"] is not on the "cd""X"-path.
The inversion will not affect the set of free colors on "F"["i"], and "d" will remain free on it.
By (1), "F"′ = "F"[1:"i"] is a valid fan, and we can set "w" = "i". 
Case2.2: "F"["i"] is on the "cd""X"-path.
Below, we can show that "F"[1:"k"] is still a fan after the inversion and "d" remains free on "F"["k"], so we can set "w" = "k".
Since "d" was free on "F"["i"] before the inversion and "F"["i"] is on the "cd""X"-path, "F"["i"] is an endpoint of the path and "c" will be free on "F"["i"] after the inversion.
The inversion will change the color of ("X","F"["i"+1]) from "d" to "c".
Thus, since "c" is now free on "F"["i"] and (1) holds, th whole "F" remains a fan.
Also, "d" remains free on "F"["k"], since "F"["k"] is not on the "cd""X"-path.
The edge coloring is valid.
This can be shown by induction on the number of colored edges.
Base case: no edge is colored, this is valid.
Induction step: suppose this was true at the end of the previous iteration.
In the current iteration, after inverting the path, "d" will be free on "X", and by the previous result, it will also be free on "w".
Rotating "F"′ does not compromise the validity of the coloring.
Thus, after setting the color of ("X","w") to "d", the coloring is still valid.
The algorithm requires at most Δ+1 colors.
In a given step, only colors "c" and "d" are used.
"F"["k"] has at most Δ colored edges, so Δ+1 colors in total ensures that we can pick "d".
This leaves Δ colors for "c".
Since there is at least one uncolored edge incident on "X", and its degree is bounded by Δ, there are most Δ-1 colors incident on "X" currently, which leaves at least one choice for "c".
Complexity.
In every iteration of the loop, one additional edge gets colored.
Hence, the loop will run formula_5 times.
Finding the maximal fan, the colors "c" and "d" and invert the "cd""X"-path can be done in formula_6 time.
Finding "w" and rotating "F"′ takes formula_7 time.
Finding and removing an edge can be done using a stack in constant time (pop the last element) and this stack can be populated in formula_5 time.
Thus, each iteration of the loop takes formula_6 time, and the total running time is formula_10.
References.
 ;templatestyles src="Reflist/styles.css" / ;