next up previous contents index CD CD Algorithms
Next: Edge Coloring Up: Graph Problems: Hard Problems Previous: Graph Partition

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 tex2html_wrap_inline29532 , 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:

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,, 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, tex2html_wrap_inline29542 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 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 gif.

XTango (see Section gif) 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 gif.  

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

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 tex2html_wrap_inline29544 approximation algorithm, where tex2html_wrap_inline29546 is the chromatic number of G. Hardness of approximation results for vertex coloring include [BGS95].

Brook's theorem states that the chromatic number tex2html_wrap_inline29548 , where tex2html_wrap_inline29550 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 gif), edge coloring (see page gif).    

next up previous contents index CD CD Algorithms
Next: Edge Coloring Up: Graph Problems: Hard Problems Previous: Graph Partition

Mon Jun 2 23:33:50 EDT 1997