Vertex Coloring

  

 

Input description: A graph G=(V,E).

Problem description: Color the vertices of V using the minimum number of colors such that for each edge , vertices i and j have different colors.

Discussion: Vertex coloring arises in a variety of scheduling and clustering applications. Compiler optimization is the canonical application for coloring, where we seek to schedule the use of a finite number of registers.     In a program fragment to be optimized, each variable has a range of times during which its value must be kept intact, in particular, after it is initialized and before its final use. Any two variables whose life spans intersect cannot be placed in the same register. Construct a graph where there is a variable associated with each vertex and add an edge between any two vertices whose variable life spans intersect. A coloring of the vertices of this graph assigns the variables to classes such that two variables with the same color do not clash and so can be assigned to the same register.  

No conflicts can occur if each vertex is colored with a distinct color. However, our goal is to find a coloring using the minimum number of colors, because computers have a limited number of registers. The smallest number of colors sufficient to vertex color a graph is known as its chromatic number.  

Several special cases of interest arise in practice:

• Can I color the graph using only two colors? - An important special case is testing whether a graph is bipartite, meaning it can be colored using two different colors.   Such a coloring of the vertices of a bipartite graph means that the graph can be drawn with the red vertices on the left and the blue vertices on the right such that all edges go from left to right. Bipartite graphs are fairly simple, yet they arise naturally in such applications as mapping workers to possible jobs. Fast, simple algorithms exist for problems such as matching (see Section ) on bipartite graphs.  

  Testing whether a graph is bipartite is easy. Color the first vertex blue, and then do a depth-first search of the graph.   Whenever we discover a new, uncolored vertex, color it opposite that of its parent, since the same color would cause a clash. If we ever find an edge where both vertices have been colored identically, then the graph cannot be bipartite. Otherwise, this coloring will be a 2-coloring, and it is constructed in O(n+m) time.

• Is the graph planar, or are all vertices of low degree? -   The famous 4-color theorem states that every planar graph can be vertex colored using at most 4 distinct colors. Efficient algorithms for finding a 4-coloring are known, although it is NP-complete to decide whether a given planar graph is 3-colorable.

  There is a very simple algorithm that finds a vertex coloring of any planar graph using at most 6 colors. In any planar graph, there exists a vertex of degree at most five. Delete this vertex and recursively color the graph. This vertex has at most five neighbors, which means that it can always be colored using one of the six colors that does not appear as a neighbor. This works because deleting a vertex from a planar graph leaves a planar graph, so we always must have a low-degree vertex to delete. The same idea can be used to color any graph of maximum degree using colors in time.

• Is this an edge coloring problem? - Certain vertex coloring problems can be modeled as edge coloring,   where we seek to color the edges of a graph G such that no two edges with a vertex in common are colored the same. The payoff is that there is an efficient algorithm that always returns a near-optimal edge coloring. Algorithms for edge coloring are the focus of Section .

Computing the chromatic number of a graph is NP-complete, so if you need an exact solution you must resort to backtracking,   which can be surprisingly effective in coloring certain random graphs. It remains hard to compute a provably good approximation to the optimal coloring, so expect no guarantees.

Incremental methods appear to be the heuristic of choice for vertex coloring.   As in the previous algorithm for planar graphs, vertices are colored sequentially, with the colors chosen in response to colors already assigned in the vertex's neighborhood. These methods vary in how the next vertex is selected and how it is assigned a color. Experience suggests inserting the vertices in nonincreasing order of degree, since high-degree vertices have more color constraints and so are most likely to require an additional color if inserted late.

Incremental methods can be further improved by using color interchange.   Observe that taking a properly colored graph and exchanging two of the colors (painting the red vertices blue and the blue vertices red) leaves a proper vertex coloring. Now suppose we take a properly colored graph and delete all but the red and blue vertices. If the remaining graph (the induced subgraph) consists of two or more connected components, we can repaint one or more of the components, again leaving a proper coloring.   After such a recoloring, some vertex v previously adjacent to both red and blue vertices might now be only adjacent to blue vertices, thus freeing v to be colored red.

Color interchange is a win in terms of producing better colorings, at a cost of increased time and implementation complexity. Implementations are described below.   Simulated annealing algorithms that incorporate color interchange to move from state to state are likely to be even more effective.

Implementations: Graph coloring has been blessed with two distinct and useful WWW resources. Michael Trick's page, http://mat.gsia.cmu.edu/COLOR/color.html, provides a nice overview of applications of graph coloring, an annotated bibliography, and a collection of over seventy graph coloring instances arising in applications such as register allocation and printed circuit board testing. Finally, it contains a C language implementation of an exact coloring algorithm, DSATUR.     Joseph C. Culberson's WWW page on graph coloring, http://web.cs.ualberta.ca/ joe/Coloring/, provides an extensive bibliography and a collection of programs to generate hard graph coloring instances.

Programs for the closely related problems of finding cliques and vertex coloring graphs were sought for the Second DIMACS Implementation Challenge, held in October 1993.   Programs and data from the challenge are available by anonymous ftp from dimacs.rutgers.edu. Source codes are available under pub/challenge/graph and test data under pub/djs, including a simple ``semi-exhaustive greedy'' scheme used in the graph coloring algorithm XRLF [JAMS91].    

Pascal implementations of backtracking algorithms for vertex coloring and several heuristics, including largest-first and smallest-last incremental orderings and color interchange, appear in [SDK83].   See Section .

XTango (see Section ) is an algorithm animation system for UNIX and X-windows,   and includes an animation of vertex coloring via backtracking.

Nijenhuis and Wilf [NW78] provide an efficient Fortran implementation of chromatic polynomials and vertex coloring by backtracking.   See Section .  

Combinatorica [Ski90] provides Mathematica implementations of bipartite graph testing, heuristic colorings, chromatic polynomials, and vertex coloring by backtracking. See Section .    

Notes: An excellent source on vertex coloring heuristics is Syslo, Deo, and Kowalik [SDK83], which includes experimental results.   Heuristics for vertex coloring include Brèlaz [Brè79], Matula [MMI72], and Turner [Tur88]. Wilf [Wil84] proved that backtracking to test whether a random graph has chromatic number k runs in constant time, dependent on k but independent of n.   This is not as interesting as it sounds, because only a vanishingly small fraction of such graphs are indeed k-colorable.

Expositions on algorithms to recognize bipartite graphs include [Man89]. Expositions on the hardness of 3-coloring graphs include [AHU74, Eve79a, Man89]. An interesting application of vertex coloring to scheduling traffic lights appears in [AHU83].  

Baase [Baa88] gives a very good description of approximation algorithms for graph coloring, including Wigderson's [Wig83] factor of approximation algorithm, where is the chromatic number of G. Hardness of approximation results for vertex coloring include [BGS95].

Brook's theorem states that the chromatic number , where is the maximum degree of a vertex of G.   Equality holds only for odd-length cycles (which have chromatic number 2) and complete graphs.  

The most famous problem in the history of graph theory is the four-color problem, first posed in 1852 and finally settled in 1976 by Appel and Haken using a proof involving extensive computation.   Any planar graph can be 5-colored using a variation of the color interchange heuristic. Despite the four-color theorem, it is NP-complete to test whether a particular planar graph requires four colors or whether three suffice. See [SK86] for an exposition on the history of the four-color problem and the proof. An efficient algorithm to four-color a graph is presented in [RSST96].

Related Problems: Independent set (see page ), edge coloring (see page ).