Misra & Gries edge-coloring algorithm

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 Δ + 1 {\displaystyle \Delta +1} colors, where Δ {\displaystyle \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. 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. For many years this algorithm was the fastest published almost-optimal algorithm for edge coloring, executing in O ( | E | | V | ) {\displaystyle O(|E||V|)} time. A faster time bound of O ( | E | | V | log ⁡ | V | ) {\displaystyle O\left(|E|{\sqrt {|V|\log |V|}}\right)} was claimed in a 1985 technical report by Gabow et al., but was never published. In 2025 a group of researchers published a faster algorithm for the same problem, with runtime O ( | E | log ⁡ Δ ) {\displaystyle O(|E|\log \Delta )} . 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:

F[1:k] is a non-empty sequence of distinct neighbors of X; Edge (X,F[1]) is uncolored; The color of (X,F[i+1]) is free on F[i] for 1 ≤ i < k. 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 cdX-path is an edge path that goes through vertex X, only contains edges colored c or d, and is maximal. (We cannot add any other edge with color c or d to the path.) 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 cdX-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 & 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. U := U − {(X,v)} end while

Proof of correctness The correctness of the algorithm is proved in three parts. First, it is shown that the inversion of the cdX-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.

… excerpt ends here. Continue reading the full article.