Misra & Gries edge coloring algorithm

Short description: Algorithm in graph theory

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 [math]\displaystyle{ \Delta+1 }[/math] colors, where [math]\displaystyle{ \Delta }[/math] 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 [math]\displaystyle{ O(|E||V|) }[/math] time. A faster time bound of [math]\displaystyle{ O\left(|E|\sqrt{|V|\log|V|}\right) }[/math] 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.

Fans

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) [math]\displaystyle{ \in }[/math] 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) [math]\displaystyle{ \in }[/math] 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

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

Proof of correctness

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.

Path inversion guarantee

Prior to the inversion, there are two cases:

1. The fan has no edge colored d. Since F is a maximal fan and d is free on F[k], this implies there is no edge with color d adjacent to u, otherwise, if there was, this edge would be after F[k], as d is free on F[k], but F was maximal, which is a contradiction. Thus, d is free on u, and since c is also free on u, the cd_u path is empty and the inversion has no effect on the graph. Set w = F[k].
2. The fan has one edge with color d. Let (u,F[x+1]) be this edge. Note that x + 1 ≠ 1 since (u,F[1]) is uncolored. Thus, d is free on F[x]. Also, x ≠ k since the fan has length k but there exists a F[x + 1]. We can now show that after the inversion, for each y ∈ {1, ..., x − 1, x + 1, ..., k}, the color of (F[y + 1], u) is free on F[y]. Note that prior to the inversion, the color of (u, F[y + 1]) is not c or d, since c is free on u and (u, F[x + 1]) has color d and the coloring is valid. The inversion only affects edges that are colored c or d, so (1) holds.

F[x] can either be in the cd_u path or not. If it is not, then the inversion will not affect the set of free colors on F[x], and d will remain free on it. We can set w = F[x]. Otherwise, we can show that F is still a fan and d remains free on F[k]. Since d was free on F[x] before the inversion and F[x] is on the path, F[x] is an endpoint of the cd_u path and c will be free on F[x] after the inversion. The inversion will change the color of (u, F[x + 1]) from d to c. Thus, since c is now free on F[x] and (1) holds, F remains a fan. Also, d remains free on F[k], since F[k] is not on the cd_u path (suppose that it is; since d is free on F[k], then it would have to be an endpoint of the path, but u and F[x] are the endpoints). Select w = F[k].

In any case, the fan F' is a prefix of F, which implies F' is also a fan.

The edge coloring is proper

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 u, 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 c(u,w) = d, the coloring is still valid.

The algorithm requires at most Δ + 1 colors

In a given step, only colors c and d are used. Since u is adjacent to at least one uncolored edge and its degree is bounded by Δ, at least one color in {1,...,Δ} is available for c. For d, F[k] may have degree Δ and no uncolored adjacent edge. Thus, a color Δ + 1 may be required.

Complexity

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 [math]\displaystyle{ O(|E|) }[/math] times. Finding the maximal fan, the colors c and d and invert the cd_u path can be done in [math]\displaystyle{ O(|V|) }[/math] time. Finding w and rotating F' takes [math]\displaystyle{ O(\deg(u))\in O(|V|) }[/math] 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 [math]\displaystyle{ O(|E|) }[/math] time. Thus, each iteration of the loop takes [math]\displaystyle{ O(|V|) }[/math] time, and the total running time is [math]\displaystyle{ O(|E|+|E||V|)=O(|E||V|) }[/math].