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 colors, where 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.[1] It is a simplification of a prior algorithm by Béla Bollobás.[2]

This algorithm is the fastest known almost-optimal algorithm for edge coloring, executing in time. A faster time bound of was claimed in a 1985 technical report by Gabow et al., but this has never been published.[3]

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

edit

Free color

edit

A color c is said to be free on a vertex u if no incident edge of u has color c.

 
A fan F = [x1,x2,x3] of v (dashed edges are uncolored), (v,x1), (v,x2), (v,x3) are the fan edges. F = [x1,x2] 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 ≤ ik is a fan edge.

Rotating a fan

edit
 
Rotating the fan F = [x1,x2,x3] 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

edit
 
Examples of cdx paths: ac,cg,gd is a red-greenc path and bd,dg is a red-oranged 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

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

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

edit
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

edit

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.

Path inversion guarantee

edit

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 cdX-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, ik 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 cdX-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 cdX-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 cdX-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 cdX-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

edit

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

edit

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

edit

In every iteration of the loop, one additional edge gets colored. Hence, the loop will run   times. Finding the maximal fan, the colors c and d and invert the cdX-path can be done in   time. Finding w and rotating F takes   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   time. Thus, each iteration of the loop takes   time, and the total running time is  .

References

edit
  1. ^ Misra, Jayadev; Gries, David (1992). "A constructive proof of Vizing's theorem" (PDF). Information Processing Letters. 41 (3): 131–133. doi:10.1016/0020-0190(92)90041-S.
  2. ^ Bollobás, Béla (1982). Graph theory. Elsevier. p. 94.
  3. ^ Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University