Misra & Gries edge coloring algorithm

A fan F=[x_1,x_2,x_3] of v (dashed edges are uncolored), (v,x_1),(v,x_2),(v,x_3) are the fan edges. F'=[x_1,x_2] is also a fan of v, but it is not maximal.

A color x of an edge (u,v) is said to be free on u if c(u,z) ≠ x for all (u,z) ${\displaystyle \in }$ E(G) : z≠v.

A fan of a vertex u 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 u
2. (F[1],u) ${\displaystyle \in }$ E(G) is uncolored
3. The color of (F[i+1],u) is free on F[i] for 1 ≤ i < k

Examples of cd_x paths: ac,cg,gd is a red-green_{_c} path and bd,dg is a red-orange_d path.

Given a fan F, any edge (F[i], X) for 1 ≤ i ≤ k is a fan edge. Let c and d be colors. A cd_X-path is an edge path that goes through vertex X, only contains edges colored c and d and is maximal (we cannot add any other edge as it would include edges with a color not in {c, d}). Note that only one such path exists for a vertex X, as at most one edge of each color can be adjacent to a given vertex.

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 (in parallel):

1. c(F[i],X)=c(F[i+1],X)
2. Uncolor (F[k],X)

This operation leaves the coloring valid, as for each i, c(F[i + 1], X) was free on (F[i], X).

Inverting a 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 X was adjacent to color c but not d, it will now be adjacent to color d, not c, freeing c for another edge adjacent to X. The flipping operation will not alter the validity of the coloring since for the endpoints, only one of {c, d} can be adjacent to the vertex, and for other members of the path, the operation only switches the color of edges, no new color is added.

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 (u, v) be any edge in U.  
        Let F[1:k] be a maximal fan of u starting at F[1] = v.
        Let c be a color that is free on u and d be a color that is free on F[k].  
        Invert the cdu path  
        Let w ∈ V(G) be such that w ∈ F, F' = [F[1]...w] is a fan and d is free on w.  
        Rotate F' and set c(u, w) = d.
        U := U − {(u, v)}
    end while

The correctness of the algorithm is proved in three parts. First, it is shown that the inversion of the cd_u path guarantees a vertex w such that w ∈ F, F' = [F[1]...w] is a fan and d is free on w. Then, it is shown that the edge coloring is proper and requires at most Δ + 1 colors.

At each step, the rotation uncolors the edge (u,w) while coloring edges (u,F[1]) and (u,v) which was previously uncolored. Thus, one additional edge gets colored. Hence, the loop will run ${\displaystyle O(|E|)}$ times. Finding the maximal fan, the colors c and d and invert the cd_u path can be done in ${\displaystyle O(|V|)}$ time. Finding w and rotating F' takes ${\displaystyle O(\deg(u))\in O(|V|)}$ time. Finding and removing the edge (u,v) can be done using a stack in constant time (pop the last element) and this stack can be populated in ${\displaystyle O(|E|)}$ time. Thus, each iteration of the loop takes ${\displaystyle O(|V|)}$ time, and the total running time is ${\displaystyle O(|E|+|E||V|)=O(|E||V|)}$.