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 $\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.

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 $O(|E||V|)$ time. A faster time bound of $O\left(|E|{\sqrt {|V|\log |V|}}\right)$ 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 F = [x₁,x₂,x₃] of v (dashed edges are uncolored), (v,x₁), (v,x₂), (v,x₃) are the fan edges. F′ = [x₁,x₂] is also a fan of v, but it is not maximal.

A fan of a vertex X is a sequence of vertices F[1:k] that satisfies the following conditions:

1. F[1:k] is a non-empty sequence of distinct neighbors of X;
2. Edge (X,F[1]) is uncolored;
3. 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

Rotating the fan F = [x₁,x₂,x₃] on the left results in the fan on the right

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

Examples of cd_x paths: ac,cg,gd is a red-green_c path and bd,dg is a red-orange_d 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. (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

Inverting the red-green_a path from the graph on the left results in the graph on the right.

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 & 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 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. (Suppose that it is; since d is free on F[k], then it would have to be an endpoint of the path, but X and F[i] are the endpoints.)

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 $O(|E|)$ times. Finding the maximal fan, the colors c and d and invert the cd_X-path can be done in $O(|V|)$ time. Finding w and rotating F′ takes $O(\Delta )\in O(|V|)$ 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 $O(|E|)$ time. Thus, each iteration of the loop takes $O(|V|)$ time, and the total running time is $O(|E|+|E||V|)=O(|E||V|)$.