# Approximate Graph Coloring by Semidefinite Programming.

Abstract. We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with min{O([[Delta].sup.1/3] [log.sup.1/2] [Delta] log n), O([n.sup.1/4] [log.sup.1/2] n)} colors where [Delta] is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first nontrivial approximation result as a function of the maximum degree [Delta]. This result can be generalized to k-colorable graphs to obtain a coloring using min{O([[Delta].sup.1-2/k] [log.sup.1/2] [Delta] log n), O([n.sup.1-3/(k+1)] [log.sup.1/2] n)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz v-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the v-function.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms, Optimization, Theory

Additional Key Words and Phrases: Approximation algorithms, chromatic number, graph coloring, NP-completeness, randomized algorithms

1. Introduction

A legal vertex coloring of a graph G(V, E) is an assignment of colors to its vertices such that no two adjacent vertices receive the same color. Equivalently, a legal coloring of G by k colors is a partition of its vertices into k independent sets. The minimum number of colors needed for such a coloring is called the chromatic number of G, and is usually denoted by [sub.[Chi]](G). Determining the chromatic number of a graph is known to be NP-hard (cf. Garey and Johnson [1979]).

Besides its theoretical significance as a canonical NP-hard problem, graph coloring arises naturally in a variety of applications such as register allocation [Briggs et al. 1989; Chaitin 1982; Chaitin et al. 1981] and timetable/examination scheduling [Berge 1973; Wood 1969]. In many applications that can be formulated as graph coloring problems, it suffices to find an approximately optimum graph coloring--a coloring of the graph with a small though non-optimum number of colors. This along with the apparent impossibility of an exact solution has led to some interest in the problem of approximate graph coloring. The analysis of approximation algorithms for graph coloring started with the work of Johnson [1974], who shows that a version of the greedy algorithm gives an O(n/log n)-approximation algorithm for k-coloring. Wigderson [1983] improved this bound by giving an elegant algorithm that uses O([n.sup.1-1/(k-1)]) colors to legally color a k-colorable graph. Subsequently, other polynomial time algorithms were provided by Blum [1994] that use O([n.sup.3/8] [log.sup.8/5] n) colors to legally color an n-vertex 3-colorable graph. This result generalizes to coloring a k-colorable graph with O([n.sup.1-1/(k-4/3)] [log.sup.8/5] n) colors. The best known performance guarantee for general graphs is due to Halldorsson [1993] who provided a polynomial time algorithm using a number of colors that is within a factor of O(n[(log log n).sup.2]/[log.sup.3] n) of the optimum.

Recent results in the hardness of approximations indicate that it may be not possible to substantially improve the results described above. Lund and Yannakakis [1993] used the results of Arora et al. [1992] and Feige et al. [1996] to show that there exists a (small) constant [Epsilon] [is greater than] 0 such that no polynomial time algorithm can approximate the chromatic number of a graph to within a ratio of [n.sup.[Epsilon]] unless P = NP. The current hardness result for the approximation of the chromatic number is due to Feige and Kilian [1996] and Hastad [1996], who show that approximating it to within [n.sup.1-[Delta]], for any [Delta] [is greater than] 0, would imply NP = RP (RP is the class of probabilistic polynomial time algorithms making one-sided error). However, none of these hardness results apply to the special case of the problem where the input graph is guaranteed to be k-colorable for some small k. The best hardness result in this direction is due to Khanna et al. [1992] who show that it is not possible to color a 3-colorable graph with 4 colors in polynomial time unless P = NP.

In this paper, we present improvements on the result of Blum [1994]. In particular, we provide a randomized polynomial time algorithm that colors a 3-colorable graph of maximum degree [Delta] with min{O([[Delta].sup.1/3] [log.sup.1/2] [Delta] log n), O([n.sup.1/4] [log.sup.1/2] n)} colors; moreover, this can be generalized to k-colorable graphs to obtain a coloring using O([[Delta].sup.1-2/k] [log.sup.1/2] [Delta] log n) or O([n.sup.1-3/(k+1)] [log.sup.1/2] n) colors. Besides giving the best known approximations in terms of n, our results are the first nontrivial approximations given in terms of [Delta]. Our results are based on the recent work of Goemans and Williamson [1995] who used an algorithm for semidefinite optimization problems (cf. Grotschel et al. [1981] and Alizadeh [1995]) to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. We follow their basic paradigm of using algorithms for semidefinite programming to obtain an optimum solution to a relaxed version of the problem, and a randomized strategy for "rounding" this solution to a feasible but approximate solution to the original problem. Motwani and Naor [1993] have shown that the approximate graph coloring problem is closely related to the problem of finding a CUT COVER of the edges of a graph. Our results can be viewed as generalizing the MAX CUT approximation algorithm of Goemans and Williamson to the problem of finding an approximate CUT COVER. In fact, our techniques also lead to improved approximations for the MAX k-CUT problem [Frieze and Jerrum 1994]. We also establish a duality relationship between the value of the optimum solution to our semidefinite program and the Lovasz v-function [Grotschel et al. 1981, 1987; Lovasz 1979]. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the v-function.

Alon and Kahale [1994] use related techniques to devise a polynomial time algorithm for 3-coloring random graphs drawn from a "hard" distribution on the space of all 3-colorable graphs. Recently, Frieze and Jerrum [1994] have used a semidefinite programming formulation and randomized rounding strategy essentially the same as ours to obtain improved approximations for the MAX k-CUT problem with large values of k. Their results required a more sophisticated version of our analysis, but for the coloring problem our results are tight up to poly-logarithmic factors and their analysis does not help to improve our bounds.

Semidefinite programming relaxations are an extension of the linear programming relaxation approach to approximately solving NP-complete problems. We thus present our work in the style of the classical LP-relaxation approach. We begin in Section 2 by defining a relaxed version of the coloring problem. Since we use a more complex relaxation than standard linear programming, we must show that the relaxed problem can be solved; this is done in Section 3. We then show relationships between the relaxation and the original problem. In Section 4, we show that (in a sense to be defined later) the value of the relaxation bounds the value of the original problem. Then, in Sections 5, 6, and 7, we show how a solution to the relaxation can be "rounded" to make it a solution to the original problem. Combining the last two arguments shows that we can find a good approximation. Section 3, Section 4, and Sections 5-7 are in fact independent and can be read in any order after the definitions in Section 2. In Section 8, we investigate the relationship between our fractional relaxations and the Lovasz v-function, showing that they are in fact dual to one another. We investigate the approximation error inherent in our formulation of the chromatic number via semi-definite programming in Section 9.

2. A Vector Relaxation of Coloring

In this section, we describe the relaxed coloring problem whose solution is in turn used to approximate the solution to the coloring problem. Instead of assigning colors to the vertices of a graph, we consider assigning (n-dimensional) unit vectors to the vertices. To capture the property of a coloring, we aim for the vectors of adjacent vertices to be "different" in a natural way. The vector k-coloring that we define plays the role that a hypothetical "fractional k-coloring" would play in a classical linear-programming relaxation approach to the problem. Our relaxation is related to the concept of an orthonormal representation of a graph [Lovasz 1979; Grotschel et al. 1981].

Definition 2.1. Given a graph G = (V, E) on n vertices, and a real number k [is greater than or equal to] 1, a vector k-coloring of G is an assignment of unit vectors [v.sub.i] from the space [R.sup.n] to each vertex i [element of] V, such that for any two adjacent vertices i and j the dot product of their vectors satisfies the inequality

<[v.sub.i], [v.sub.j]> [is less than or equal to] -1/k - 1.

The definition of an orthonormal representation [Lovasz 1979; Grotschel et al. 1981] requires that the given dot products be equal to zero, a weaker requirement than the one above.

3. Solving the Vector Coloring Problem

In this section, we show how the vector coloring relaxation can be solved using semidefinite programming. The methods in this section closely mimic those of Goemans and Williamson [1995].

To solve the problem, we need the following auxiliary definition:

Definition 3.1. Given a graph G = (V, E) on n vertices, a matrix k-coloring of the graph is an n x n symmetric positive semidefinite matrix M, with [m.sub.ii] = 1 and [m.sub.ij] [is less than or equal to] -1/(k - 1) if {i, j} [element of] E.

We now observe that matrix and vector k-colorings are in fact equivalent (cf. Goemans and Williamson [1995]). Thus, to solve the vector coloring relaxation, it will suffice to find a matrix k-coloring.

FACT 3.2. A graph has a vector k-coloring if and only if it has matrix k-coloring. Moreover, a vector (k + [Epsilon])-coloring can be constructed from a matrix k-coloring in time polynomial in n and log(1/[Epsilon]).

Note that an exact solution cannot be found, as some of the values in it may be irrational.

PROOF. Given a vector k-coloring {[v.sub.i]}, the matrix k-coloring is defined by [m.sub.ij] = ([v.sub.i], [v.sub.j]}. For the other direction, it is well known that for every symmetric positive definite matrix M there exists a square matrix U such that [UU.sup.T] = M (where [U.sup.T] is the transpose of U). The rows of U are vectors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that form a vector k-coloring of G.

An [Delta]-close approximation to the matrix U can be found in time polynomial in n and log(1/[Delta]) using the Incomplete Cholesky Decomposition [Goemans and Williamson 1995; Golub and Van Loan 1983]. (Here by [Delta]-close we mean a matrix U' such that [U'U'.sup.T] - M has [L.sub.[infinity]] norm less than [Delta].) This, in turn, gives a vector (k + [Epsilon])-coloring of the graph, provided [Delta] is chosen appropriately. []

LEMMA 3.3. If a graph G has a vector k-coloring, then a vector (k + [Epsilon])-coloring of the graph can be constructed in time polynomial in k, n, and log(1/[Epsilon]).

PROOF. Our proof is similar to those of Lovasz [1979] and Goemans-Williamson [1995]. We construct a semidefinite optimization problem (SDP) whose optimum is -1/(k - 1) when k is the smallest real number such that a matrix k-coloring of G exists. The optimum solution also provides a matrix k-coloring of G.
```minimize     a
where        {[m.sub.ij]} is positive semidefinite
subject to   [m.sub.ij] [is less than   if (i, j) [element of] E
or equal to] [Alpha]
[m.sub.ij] = [m.sub.ji]
[m.sub.ii] = 1.
```

Consider a graph that has a vector (and matrix) k-coloring. This means there is a solution to the above semidefinite program with [Alpha] = -1/(k - 1). The ellipsoid method or other interior-point-based methods [Grotschel et al. 1981; Alizadeh 1995] can be employed to find a feasible solution where the value of the objective is at most -1/(k - 1) + [Delta] in time polynomial in n and log 1/[Delta]. This implies that for all {i, j} [element of] E, [m.sub.ij] is at most [Delta] -1/(k - 1), which is at most -1/(k + [Epsilon] - 1) for [Epsilon] = 2[Delta][(k - 1).sup.2], provided [Delta] [is less than or equal to] 1/2(k - 1). Thus, a matrix (k + [Epsilon])-coloring can be found in time polynomial in k, n and log(1/[Epsilon]). From the matrix coloring, the vector coloring can be found in polynomial time as was noted in the previous lemma. []

For the remainder of this paper, we will ignore the [Epsilon] error term in Lemma 3.3 because it can be made so small as to be irrelevant to our analysis.

4. Relating the Original and Relaxed Solutions

In this section, we show that our vector coloring problem is a useful relaxation because the solution to it is related to the solution of the original problem. In order to understand the quality of the relaxed solution, we need the following geometric lemma:

LEMMA 4.1. For all positive integers k and n such that k [is less than or equal to] n + 1, there exist k unit vectors in [R.sup.n] such that the dot product of any distinct pair is -1/(k - 1).

PROOF. Clearly, it suffices to prove the lemma for n = k - 1. (For other values of n, we make the coordinates of the vectors 0 in all but the first k - 1 coordinates.) We begin by proving the claim for n = k. We explicitly provide unit vectors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i [is not equal to] j. The vector [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [(1/k(k - 1)).sup.1/2] in all coordinates except the ith coordinate. In the ith coordinate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [((k - 1)/k).sup.1/2]. It is easy to verify that the vectors are unit length and that their dot products are exactly (-1/(k - 1)).

As given, the vectors are in a k-dimensional space. Note, however, that the dot product of each vector with the all-1's vector is 0. This shows that all k of the vectors are actually in a (k - 1)-dimensional hyperplane of the k-dimensional space. This proves the lemma. []

COROLLARY 4.2. Every k-colorable graph G has a vector k-coloring.

PROOF. Bijectively map the k colors to the k vectors defined in the previous lemma. []

Note that a graph is vector 2-colorable if and only if it is 2-colorable. Lemma 4.1 is tight in that it provides the best possible value for minimizing the maximum dot-product among k unit vectors. This can be seen from the following lemma:

LEMMA 4.3. Let G be vector k-colorable and let i be a vertex in G. The induced subgraph on the neighbors of i is vector (k - 1)-colorable.

PROOF. Let [v.sub.1], ..., [v.sub.n] be a vector k-coloring of G and assume without loss of generality that [v.sub.i] = (1, 0, 0, ..., 0). Associate with each neighbor j of i a vector [v'.sub.j] obtained by projecting [v.sub.j] onto coordinates 2 through n and then scaling it up so that [v'.sub.j] has unit length. It suffices to show that for any two adjacent vertices j and j' in the neighborhood of i, <[v'.sub.j], [v'.sub.j],) [is less than or equal to] -1/(k - 2).

Observe first that the projection of [v.sub.j] onto the first coordinate is negative and has magnitude at least 1/(k - 1). This implies that the scaling factor for [v'.sub.j] is at least (k- 1)/[(k(k - 2)).sub.1/2]. Thus,

<[v'.sub.j], [v'.sub.j']> [is less than or equal to] [(k - 1).sup.2]/k(k - 2) (<[v.sub.j], [v.sub.j']> - 1/[(k - 1).sup.2]) [is less than or equal to] -1/k - 2]. []

A simple induction using the above lemma shows that any graph containing a (k + 1)-clique is not k-vector colorable. Thus, the "vector chromatic number" lies between the clique and chromatic number. This also shows that the analysis of Lemma 4.1 is tight in that -1/(k - 1) is the minimum possible value of the maximum of the dot-products of k vectors.

In the next few sections, we prove the harder part, namely, if a graph has a vector k-coloring then it has an O([[Delta].sup.1-2/k]) and an O([n.sup.1-3/(k+1))-coloring.

5. Semicolorings

Given the solution to the relaxed problem, our next step is to show how to "round" the solution to the relaxed problem in order to get a solution to the original problem. Both of the rounding techniques we present in the following sections produce the coloring by working through an almost legal semicoloring of the graph, as defined below.

Definition 5.1. A k-semicoloring of a graph G is an assignment of k colors to at least half its vertices such that no two adjacent vertices are assigned the same color.

An algorithm for semicoloring leads naturally to a coloring algorithm as shown by the following lemma. The algorithm uses up at most a logarithmic factor more colors than the semicoloring algorithm. Furthermore, we do not even lose this logarithmic factor if the semicoloring algorithm uses a polynomial number of colors (which is what we will show we use).

LEMMA 5.2. If an algorithm A can [k.sub.i]-semicolor any i-vertex subgraph of graph G in randomized polynomial time, where [k.sub.i] increases with i, then A can be used to O([k.sub.n] log n)-color G. Furthermore, if there exists [Epsilon] [is greater than] 0 such that for all i, [k.sub.i] = [Omega]([i.sup.[Epsilon]]), then A can be used to color G with O([k.sub.n]) colors.

PROOF. We show how to construct a coloring algorithm A' to color any subgraph H of G. A' starts by using A to semicolor H. Let S be the subset of vertices that have not been assigned a color by A. Observe that |S| [is less than or equal to] |V(H)|/2. A' fixes the colors of vertices not in S, and then recursively colors the induced subgraph on S using a new set of colors.

Let [c.sub.i] be the maximum number of colors used by A' to color any i-vertex subgraph. Then [c.sub.i] satisfies the recurrence

[c.sub.i] [is less than or equal to] [c.sub.i/2] + [k.sub.i].

It is easy to see that any [c.sub.i] satisfying this recurrence must satisfy [c.sub.i] [is less than or equal to] [k.sub.i] log i. In particular this implies that [c.sub.n] [is less than or equal to] O([k.sub.n] log n). Furthermore, for the case where [k.sub.i] = [Omega]([i.sup.[Epsilon]]), the above recurrence is satisfied only when [c.sub.i] = [Theta]([k.sub.i]). []

Using the above lemma, we devote the next two sections to algorithms for transforming vector colorings into semicolorings.

6. Rounding via Hyperplane Partitions

We now focus our attention on vector 3-colorable graphs, leaving the extension to general k for later. Let [Delta] be the maximum degree in a graph G. In this section, we outline a randomized rounding scheme for transforming a vector 3-coloring of G into an [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII])-semicoloring, and thus into an [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII])-coloring of G. Combining this method with a technique of Wigderson [1983] yields an O([n.sup.0.386])-coloring of G. The method is based on that of Goemans and Williamson [1995] and is weaker than the method we describe in the following section; however, it introduces several of the ideas we will use in the more powerful algorithm.

Assume we are given a vector 3-coloring [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Recall that the unit vectors [v.sub.i] and [v.sub.j] associated with an adjacent pair of vertices i and j have a dot product of at most -1/2, implying that the angle between the two vectors is at least 2[Pi]/3 radians (120 degrees).

Definition 6.1. Consider a hyperplane H. We say that H separates two vectors if they do not lie on the same side of the hyperplane. For any edge {i, j} [element of] E, we say that the hyperplane H cuts the edge if it separates the vectors [v.sub.i] and [v.sub.j].

In the sequel, we use the term, random hyperplane, to denote the unique hyperplane containing the origin and having as its normal a random unit vector v uniformly distributed on the unit sphere [S.sub.n]. The following lemma is a restatement of Lemma 1.2 of Goemans-Williamson [1995].

LEMMA 6.2. [GOEMANS-WILLIAMSON 1995]. Given two vectors at an angle of [Theta], the probability that they are separated by a random hyperplane is exactly [Theta]/[Pi].

We conclude that given a vector 3-coloring, for any edge {i, j} [element of] E, the probability that a random hyperplane cuts the edge is exactly 2/3. It follows that the expected fraction of the edges in G that are cut by a random hyperplane is exactly 2/3. Suppose that we pick r random hyperplanes independently. Then, the probability that an edge is not cut by one of these hyperplanes is [(1/3).sup.r], and the expected fraction of the edges not cut is also [(1/3).sup.r].

We claim that this gives us a good semicoloring algorithm for the graph G. Notice that r hyperplanes can partition [R.sup.n] into at most [2.sup.r] distinct regions. (For r [is less than or equal to] n, this is tight since r hyperplanes create exactly [2.sup.r] regions.) An edge is cut by one of these r hyperplanes if and only if the vectors associated with its end-points lie in distinct regions. Thus, we can associate a distinct color with each of the [2.sup.r] regions and give each vertex the color of the region containing its vector. The expected number of edges whose end-points have the same color is [(1/3).sup.r]m, where m is the number of edges in E.

THEOREM 6.3. If a graph has a vector 3-coloring, then it has an ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII])-semicoloring that can be constructed from the vector 3-coloring in polynomial time with high probability.

PROOF. We use the random hyperplane method just described. Fix r = 2 + ??[log.sub.3] [Delta]??, and note that [(1/3).sup.r] [is less than or equal to] 1/9[Delta] and that [2.sup.r] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As noted above, r hyperplanes chosen independently at random will cut an edge with probability 1 - 1/9[Delta]. Thus, the expected number of edges that are not cut is m/9[Delta] [is less than or equal to] n/18 [is less than] n/8, since the number of edges is at most n[Delta]/2. By Markov's inequality (cf. [Motwani and Naor 1993, p. 46]) the probability that the number of uncut edges is more than twice the expected value is at most 1/2. Thus, with probability at least 1/2, we get a coloring with at most n/4 uncut edges. Deleting one endpoint of each such edge leaves a set of 3n/4 colored vertices with no uncut edges--that is, a semicoloring.

Repeating the entire process t times means that we will find a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]-semicoloring with probability at least 1 - 1/[2.sup.t]. []

Noting that [log.sub.3]2 [is less than] 0.631 and that [Delta] [is less than or equal to] n, this theorem and Lemma 5.2 implies a semicoloring using O([n.sup.0.631]) colors.

By varying the number of hyperplanes, we can arrange for a trade-off between the number of colors used and the number of edges that violate the resulting coloring. This may be useful in some applications where a nearly legal coloring is good enough.

6.1. WIGDERSON'S ALGORITHM. Our coloring can be improved using the following idea due to Wigderson [1983]. Fix a threshold value [Delta]. If there exists a vertex of degree greater than [Delta], pick any one such vertex and 2-color its neighbors (its neighborhood is vector 2-colorable and hence 2-colorable). The colored vertices are removed and their colors are not used again. Repeating this as often as possible (or until half the vertices are colored) brings the maximum degree below 8 at the cost of using at most 2n/[Delta] colors. At this point, we can semicolor the remainder with O([[Delta].sup.0.631]) colors. Thus, we can obtain a semicoloring using O(n/[Delta] + [[Delta].sup.0.631]) colors. The optimum choice of [Delta] is around [n.sup.0.613], which implies a semicoloring using O([n.sup.0.387]) colors. This semicoloring can be used to legally color G using O([n.sup.0.387]) colors by applying Lemma 5.2.

COROLLARY 6.1.1. A 3-colorable graph with n vertices can be colored using O([n.sup.0.387]) colors by a polynomial time randomized algorithm.

The bound just described is (marginally) weaker than the guarantee of a O([n.sup.0.375]) coloring due to Blum [1994]. We now improve this result by constructing a semicoloring with fewer colors.

7. Rounding via Vector Projections

In this section, we start by proving the following more powerful version of Theorem 6.3. A simple application of Wigderson's technique to this algorithm yields our final coloring algorithm.

THEOREM 7.1. For every integer function k = k(n), a vector k-colorable graph with maximum degree [Delta] can be semi-colored with at most O([[Delta].sup.1-2/k] [square root of ln[Delta]]) colors in probabilistic polynomial time.

As in the previous section, this has immediate consequences for approximate coloring.

PROOF. Given a vector k-coloring, we show that it is possible to extract an independent set of size [Omega](n/([[Delta].sup.1-2/k] [square root of ln [Delta]])). If we assign one color to this set and recurse on the rest of the vertices, we will end up using O([[Delta].sup.1-2/k] [square root of ln [Delta]]) colors in all to assign colors to half the vertices and the result follows. To find such a large independent set, we give a randomized procedure for selecting an induced subgraph with n' vertices and m' edges such that E[n' - m'] = [Omega](n/([[Delta].sup.1-2/k] [square root of ln [Delta]])). It follows that with a polynomial number of repeated trials, we have a high probability of choosing a subgraph with n' - m' = [Omega](n/([[Delta].sup.1-2/k] [square root of ln [Delta]])). Given such a graph, we can delete one endpoint of each edge, leaving an independent set of size n' - m' = [Omega](n/([[Delta].sup.1-2/k] [square root of ln [Delta]])), as desired.

We now give the details of the construction. Suppose we have a vector k-coloring assigning unit vectors [v.sub.i] to the vertices. We fix a parameter c = [c.sub.k,[Delta]] to be specified later. We choose a random n-dimensional vector r according to a distribution to be specified soon. The subgraph consists of all vertices i with [v.sub.i] [multiplied by] r [is greater than or equal to] c. Intuitively, since endpoints of an edge have vectors pointing away from each other, if the vector associated with a vertex has a large dot product with r, then the vector corresponding to an adjacent vertex will not have such a large dot product with r and hence will not be selected. Thus, only a few edges are likely to be in the induced subgraph on the selected set of vertices.

To complete the specification of this algorithm and to analyze it, we need some basic facts about some probability distributions in [R.sub.n].

7.1. PROBABILITY DISTRIBUTIONS IN [R.sub.n]. Recall that the standard normal distribution has the density function [Phi](x) = 1/[(2[Pi]).sup.1/2] exp([-x.sup.2]/2) with distribution function [Phi](x), mean 0, and variance 1. A random vector r = ([r.sub.1], ..., [r.sub.n]) is said to have the n-dimensional standard normal distribution if the components [r.sub.i] are independent random variables, each component having the standard normal distribution. It is easy to verify that this distribution is spherically symmetric, in that the direction specified by the vector r is uniformly distributed. (Refer to Feller [1969, v. II], Knuth [1971, v. 2], and Renyi [1970] for further details about the higher dimensional normal distribution.)

Subsequently, the phrase "random d-dimensional vector" will always denote a vector chosen from the d-dimensional standard normal distribution. A crucial property of the normal distribution which motivates its use in our algorithm is the following theorem paraphrased from Renyi [1970] (see also Section III.4 of Feller [1968, v. II]).

THEOREM 7.1.1. (THEOREM IV.16.3 [RENYI 1970]). Let r = ([r.sub.1], ..., [r.sub.n]) be a random n-dimensional vector. The projections of r onto two lines [l.sub.1] and [l.sub.2] are independent (and normally distributed) if and only if [l.sub.1] and [l.sub.2] are orthogonal.

Alternatively, we can say that under any rotation of the coordinate axes, the projections of r along these axes are independent standard normal variables. In fact, it is known that the only distribution with this strong spherical symmetry property is the n-dimensional standard normal distribution. The latter fact is precisely the reason behind this choice of distribution(1) in our algorithm. In particular, we will make use of the following corollary to the preceding theorem.

COROLLARY 7.1.2. Let u be any unit vector in [R.sub.n]. Let r = ([r.sub.1], ..., [r.sub.n]) be a random vector (of i.i.d, standard normal variables). The projection of r along u, given by dot product <u, r>, is distributed according to the standard (1-dimensional) normal distribution.

It turns out that even if r is a random n-dimensional unit vector, the above corollary still holds in the limit: as n grows, the projections of r on orthogonal lines approach (scaled) independent normal distributions. Thus using a random unit vectors for our projection turns out to be equivalent to using random normal vectors in the limit, but is messier to analyze.

Let N(x) denote the tail of the standard normal distribution. That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We will need the following well-known bounds on the tail of the standard normal distribution. (See, for instance, Lemma VII.2 of Feller [1968, v. I].)

LEMMA 7.1.3. For every x [is greater than] 0,

[Phi](x)(1/x - 1/[x.sup.3]) [is less than] N(x) [is less than] [Phi](x) [multiplied by] 1/x.

PROOF. The proof is immediate from inspection of the following equations relating the three quantities in the desired inequality to integrals involving [Phi](x), and the fact [Phi](x)/x is finite for every x [is greater than] 0.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

7.2. THE ANALYSIS. We are now ready to complete the specification of the coloring algorithm. Recall that our goal is to repeatedly strip away large independent sets from the graph. We actually set an easier intermediate goal: find an induced subgraph with a large number n' of vertices and a number m' [much less than] n' of edges. Given such a graph, we can delete one endpoint of each edge to leave an independent set on n' - m' vertices that can be colored and removed.

As discussed above, to find this sparse graph, we choose a random vector r and take all vertices whose dot product with r exceeds a certain value c. Let the induced subgraph on these vertices have n' vertices and m' edges. We show that for sufficiently large c, n' [much greater than] m' and we get an independent set of size roughly n'. Intuitively, this is true for the following reason. Any particular vertex has some particular probability p = p(c) of being near r and thus being "captured" into our set. However, if two vertices are adjacent, the probability that they both land near r is quite small because the vector coloring has placed them far apart. For example, in the case of 3-coloring, when the probability that a vertex is captured is p, the probability that both endpoints of an edge are captured is roughly [p.sup.4] (this is counter the intuition that the probability should go as [p.sup.2], and follows from the fact that we force adjacent vertices to be far apart--see below). It follows that we end up capturing (in expectation) a set of pn vertices that contains (in expectation) only [p.sup.4]m [is less than] [p.sup.4][Delta]n edges in a degree-[Delta] graph. In such a set, at least pn - [p.sup.4][Delta]n of the vertices have no incident edges, and thus form an independent set. We would like this independent set to be large. Clearly, we need to make p small enough to ensure [p.sup.4][Delta]n [much less than] pn, meaning p [much less than] [[Delta].sup.-1/3]. Taking p much smaller only decreases the size of the independent set, so it turns out that our best choice is to take p [approximately equals] [[Delta].sup.-1/3]/2, yielding an independent set of size [Omega](n[[Delta].sup.-1/3]). Repeating this capture process many times therefore achieves an O([[Delta].sup.1/3]) coloring.

We now formalize the intuitive argument. The vector r will be a random n-dimensional vector. We precisely compute the expectation of n', the number of vertices captured, and the expectation of m', the number of edges in the induced graph of the captured vertices. We first show that when r is a random normal vector and our projection threshold is c, the expectation of n' - m' exceeds n(N(c) - [Delta]N(ac)) for a certain constant a depending on the vector chromatic number. We also show that N(ac) grows roughly as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (For the case of 3-coloring we have a = 2, and thus if N(c) = p, then N(ac) [approximately equals] [p.sup.4].) By picking a sufficiently large c, we can find an independent set of size [Omega](N(c)). (In the following lemma, n' and m' are functions of c: we do not make this dependence explicit.)

LEMMA 7.2.1. Let a = (2(k - 1)/[(k - 2)).sup.1/2]. Then for any c, E[n' - m'] [is greater than] n(N(c) - [Delta] N(ac)/2).

PROOF. We first bound E[n'] from below. Consider a particular vertex i with assigned vector [v.sub.i]. The probability that it is in the selected set is just P[[v.sub.i] [multiplied by] r [is greater than or equal to] c]. By Corollary 7.1.2, [v.sub.i] [multiplied by] r is normally distributed and thus this probability is N(c). By linearity of expectations, the expected number of selected vertices E[n'] = nN(c).

Now we bound E[m'] from above. Consider an edge with endpoint vectors [v.sub.1] and [v.sub.2]. The probability that this edge is in the induced subgraph is the probability that both endpoints are selected, which is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the expression follows from Corollary 7.1.2 applied to the preceding probability expression. We now observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It follows that the probability that both endpoints of an edge are selected is at most N(2ac) [is less than or equal to] N(ac). If the graph has maximum degree [Delta], then the total number of edges is at most n[Delta]/2. Thus the expected number of selected edges, E[m'], is at most n[Delta]N(ac)/2.

Combining the previous arguments, we deduce that

E[n' - m'] [is greater than or equal to] nN(c) - n[Delta] N(ac)/2. []

We now determine the a c such that [Delta]N(ac) [is less than] N(c). This will give us an expectation of at least N(c)/2 in the above lemma. Using the bounds on N(x) in Lemma 7.1.3, we find that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(The last equation holds since a = (2(k - 1)/[(k - 2))].sup.1/2] [is greater than] [square root of 2].) Thus, if we choose c so that 1 - 1/[c.sup.2] [is greater than or equal to] 1/[square root of 2] and exp([a.sup.2] - 1)[c.sup.2]/2 [is greater than or equal to] [Delta], then we get [Delta]N(ac) [is less than] N(c). Both conditions are satisfied, for sufficiently large [Delta], if we set

c = [square root of 2 (k - 2)/k ln [Delta]].

(For smaller values of [Delta], we can use the greedy [Delta] + 1-coloring algorithm to get a color from the graph with a bounded number of colors, where the bound is independent of n.)

For this choice of c, we find that the independent set that is found has size at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as desired. This concludes the proof of Lemma 7.1.

7.3. ADDING WIGDERSON'S TECHNIQUE. To conclude, we now determine absolute approximation ratios independent of [Delta]. This involves another application of Wigderson's technique. If the graph has any vertex of large degree, then we use the fact that its neighborhood is large and is vector (k - 1)-chromatic, to find a large independent set in its neighborhood. If no such vertex exists, then the graph has small maximum degree, so we can use Lemma 7.1 to find a large independent set in the graph. After extracting such an independent set, we recurse on the rest of the graph. The following lemma describes the details, and the correct choice of the threshold degree.

LEMMA 7.3.1. For every integer function k = k(n), any vector k-colorable graph on n vertices can be semicolored with O([n.sup.1-3/(k+1) [log.sup.1/2] n) colors by a probabilistic polynomial time algorithm.

PROOF. Given a vector k-colorable graph G, we show how to find an independent set of size [Omega]([n.sup.3/(k+1)]/[log.sup.1/2] n) in the graph. Assume, by induction on k, that there exists a constant c [is greater than] 0 such that we can find an independent set of size [ci.sup.3/(k'+ 1])/([log.sup.1/2] i) in any k'-vector chromatic graph on i nodes, for k' [is less than] k. We now prove the inductive assertion for k.

Let [[Delta].sub.k] = [[Delta].sub.k](n) = [n.sup.k/(k+1)]. If G has a vertex of degree greater than [[Delta].sub.k](n), then we find a large independent set in the neighborhood of G. By Lemma 4.3, the neighborhood is vector (k - 1)-colorable. Hence, we can find in this neighborhood, an independent set of size at least c[([[Delta].sub.k]).sup.3/k]/([log.sup.1/2] [[Delta].sub.k]) [is greater than or equal to] [cn.sup.3/(k+1)]/([log.sup.1/2] n). If G does not have a vertex of degree greater than [[Delta].sub.k](n), then by Lemma 7.1, we can find an independent set of size at least cn/[([[Delta].sub.k]).sup.1-2/k]/[log.sup.1/2] [[Delta].sub.k] [is greater than or equal to] [cn.sup.3/(k+1)]/[log.sup.1/2] n in G. This completes the induction.

By now assigning a new color to each such independent set, we find that we can color at least n/2 vertices, using up at most O([n.sup.1-3/(k+1)] [log.sup.1/2] n) colors. []

The semicolorings guaranteed by Lemmas 7.1 and 7.3.1 can be converted into colorings using Lemma 5.1, yielding the following theorem:

THEOREM 7.3.2. Any vector k-colorable graph on n nodes with maximum degree [Delta] can be colored, in probabilistic polynomial time, using min{O([[Delta].sup.1-2/k][square root of ln [Delta]] log n), O([n.sup.1-3/(k+ 1)] [square root of ln n)]} colors.

8. Duality Theory

The most intensively studied relaxation of a semidefinite programming formulation to date is the Lovasz v-function [Grotschel et al. 1981, 1987; Lovasz 1979]. This relaxation of the clique number of a graph led to the first polynomial-time algorithm for finding the clique and chromatic numbers of perfect graphs. We now investigate a connection between v and a close variant of the vector chromatic number.

Intuitively, the clique and coloring problems have a certain "duality" since large cliques prevent a graph from being colored with few colors. Indeed, it is the equality of the clique and chromatic numbers in perfect graphs that lets us compute both in polynomial time. We proceed to formalize this intuition. The duality theory of linear programming has an extension to semidefinite programming. With the help of Eva Tardos and David Williamson, we have shown that in fact the v-function and a close variant of the vector chromatic number are semidefinite programming duals to one another and are therefore equal.

We first define the variant.

Definition 8.1. Given a graph G = (V, E) on n vertices, a strict vector k-coloring of G is an assignment of unit vectors [u.sub.i] from the space [R.sup.n] to each vertex i [element of] V, such that for any two adjacent vertices i and j the dot product of their vectors satisfies the equality

<[u.sub.i], [u.sub.j]> = - 1/k - 1.

As usual we say that a graph is strictly vector k-colorable if it has a strict vector k-coloring. The strict vector chromatic number of a graph is the smallest real number k for which it has a strict vector k-coloring. It follows from the definition that the strict vector chromatic number of any graph is lower bounded by the vector chromatic number.

THEOREM 8.2. The strict vector chromatic number of G is equal to v([bar]G).

PROOF. The dual of our strict vector coloring semidefinite program is as follows (cf. [Alizadeh 1995]):

maximize - [Sigma] [p.sub.ii]

where {[p.sub.ij]} is positive semidefinite

subject to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By duality, the value of this semidefinite program is - 1/(k - 1) where k is the strict vector chromatic number. Our goal is to prove k = v. As before, the fact that {[p.sub.ii]} is positive semidefinite means we can find vectors [v.sub.i] such that [p.sub.ij] = <[v.sub.i], [v.sub.j]>. The last constraint says that the vectors v form an orthogonal labeling [Grotschel et al. 1987], that is, that <[v.sub.i], [v.sub.j]> = 0 for (i, j) [is not an element of] E. We now claim that the above optimization problem can be reformulated as follows:

maximize - [Sigma] <[v.sub.i], [v.sub.i]>/[[Sigma].sub.i [is not equal to] j] <[v.sub.i], [v.sub.j]>

over all orthogonal labelings {[v.sub.i]}. To see this, consider an orthogonal labeling and define [Mu] = [[Sigma].sub.i [is not an equal to] j] <[v.sub.i], [v.sub.j]>. Note this is the value of the first constraint in the first formulation of the dual (that is, the constraint is [Mu] [is less than or equal to] 1) and of the denominator in the second formulation. Then, in an optimum solution to the first formulation, we must have [Mu] - 1, since otherwise we can divide each [v.sub.i] by [square root of [Mu]] and get a feasible solution with a larger objective value. Thus, the optimum of the second formulation is at least as large as that of the first. Similarly, given any optimum {[v.sub.i]} for the second formulation, [v.sub.i]/[square root of [Mu]] forms a feasible solution to the first formulation with the same value. Thus, the optima are equal. We now manipulate the second formulation.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It follows from the last equation that the strict vector chromatic number is

max [[Sigma].sub.i,j] <[v.sub.i], [v.sub.j]>/[Sigma] <[v.sub.i], [v.sub.i]>.

However, by the same argument as was used to reformulate the dual, this is equal to the problem of maximizing [[Sigma].sub.i,j] <[v.sub.i], [v.sub.j]> over all orthogonal labelings such that [Sigma] <[v.sub.i], [v.sub.j]> [is less than or equal to] 1. This is simply Lovasz's [v.sub.3] formulation of the v-function [Grotschel et al. 1987, page 287].

9. The Gap between Vector Colorings and Chromatic Numbers

The performance of our randomized rounding approach seems far from optimum. In this section we ask why, and show that the problem is not in the randomized rounding but in the gap between the original problem and its relaxation. We investigate the following question: given a vector k-colorable graph G, how large can its chromatic number be in terms of k and n? We will show that a graph with chromatic number [n.sup.[Omega](1)] can have a bounded vector chromatic number. This implies that our technique is tight in that it is not possible to guarantee a coloring with [n.sup.o(1)] colors on all vector 3-colorable graphs.

Definition 9.1. The Kneser graph K(m, r, t) is defined as follows: the vertices are all possible r-sets from a universe of size m; and, the vertices [v.sub.i] and [v.sub.j] are adjacent if and only if the corresponding r-sets satisfy |[S.sub.i] [intersection] [S.sub.j]| [is less than] t.

We will need following theorem of Milner [1968] regarding intersecting hypergraphs. Recall that a collection of sets is called an antichain if no set in the collection contains another.

THEOREM 9.2. [MILNER 1968]. Let [S.sub.1], ..., [S.sub.[Alpha]] be an antichain of sets from a universe of size m such that, for all i and j,

|[S.sub.i] [intersection] [S.sub.j]| [is greater than] t.

Then, it must be the case that
```[Alpha] [is less than or equal to] (m)
(m + t + 1/2).
```

Notice that using all q-sets, for q = (m + t + 1)/2, gives a tight example for this theorem.

The following theorem establishes that the Kneser graphs have a large gap between their vector chromatic number and chromatic numbers.

THEOREM 9.3. Let n = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the number of vertices of the graph K(m, r, t). For r = m/2 and t = m/8, the graph K(m, r, t) is vector 3-colorable but has a chromatic number at least [n.sup.0.0113].

PROOF. We prove a lower bound on the Kneser graph's chromatic number [Chi] by establishing an upper bound on its independence number [Alpha]. It is easy to verify that the [Alpha] in Milner's theorem is exactly the independence number of the Kneser graph. To bound [Chi], observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the above sequence, the fourth line uses the approximation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for every [Beta] [element of] (0, 1), where [c.sub.[Beta]] is a constant depending only on [Beta]. Using the inequality

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we obtain m [is greater than or equal to] lg n and thus

[Chi] [is greater than or equal to] [(1.007864).sup.lgn] = [n.sup.lg 1.007864] [approximately equals] [n.sup.0.0113].

Finally, it remains to show that the vector chromatic number of this graph is 3. This follows by associating with each vertex [v.sub.i] an m-dimensional vector obtained from the characteristic vector of the set [S.sub.i]. In the characteristic vector, +1 represents an element present in [S.sub.i] and -1 represents elements absent from [S.sub.i]. The vector associated with a vertex is the characteristic vector of [S.sub.i] scaled down by a factor of [square root of m] to obtain a unit vector. Given vectors corresponding to sets [S.sub.i] and [S.sub.j], the dot product gets a contribution of -1/m for coordinates in [S.sub.i][Delta][S.sub.j] and +1/m for the others. (Here A[Delta]B represents the symmetric difference of the two sets, that is, the set of elements that occur in exactly one of A or B.) Thus, the dot product of two adjacent vertices, or sets with intersection at most t, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This implies that the vector chromatic number is 3. []

More refined calculations can be used to improve this bound somewhat.

THEOREM 9.4. There exists a Kneser graph K(m, r, t), that is 3-vector colorable but has chromatic number exceeding [n.sup.0.016101], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the number of vertices in the graph. Further, for large k, there exists a Kneser graph K(m, r, t) that is k-vector colorable but has chromatic number exceeding [n.sup.0.0717845].

PROOF. The basic idea is to improve the bound on the vector chromatic number of the Kneser graph using an appropriately weighted version of the characteristic vectors. We use weights a and -1 to represent presence and absence, respectively, of an element in the set corresponding to a vertex in the Kneser graph, with appropriate scaling to obtain a unit vector. The value of a that minimizes the vector chromatic number can be found by differentiation and is

A = -1 + mr/[r.sup.2] - rt - mt/[r.sup.2] - rt.

Setting a = A proves that the vector chromatic number is at most

m(r - t)/[r.sup.2] - mt.

At the same time, using Milner's Theorem proves that the exponent of the chromatic number is at least

1-(m - t)log(2m/(m - t)) + (m + t)log(2m/(m + t))/2((m - r)log(m/(m - r)) + r log(m/r)).

By plotting these functions, we have shown that there is a set of values with vector chromatic number 3 and chromatic number at least [n.sup.0.016101]. For large constant vector chromatic numbers, the limiting value of the exponent of the chromatic number is roughly 0.0717845. []

10. Conclusions

The Lovasz number of a graph has been a subject of active study due to the close connections between this parameter and the clique and chromatic numbers. In particular, the following "sandwich theorem" was proved by Lovasz [1979] (see Knuth [1994] for a survey).

(1) [Omega](G) [is less than or equal to] v([bar]G) [is less than or equal to] [Chi](G).

This led to the hope that the following question may have an affirmative answer. Does there exist [Epsilon], [Epsilon]' [is greater than] 0 such that, for any graph G on n vertices

(2) v([bar]G)/[n.sup.1-[Epsilon] [is less than or equal to] [Omega](G) [is less than or equal to] v([bar]G) [is less than or equal to] [Chi](G) [is less than or equal to] v([bar]G) x [n.sup.1-[Epsilon]'?

Our work in this paper proves a weak but nontrivial upper bound on the chromatic number of G in terms of v([bar]G). However, this is far from achieving the bound conjectured above and subsequent to our work, two results have ended up answering this question negatively. Feige [1995] has shown that for every [Epsilon] [is greater than] 0, there exist families of graphs for which [Chi](G) [is greater than] v([bar]G)[n.sup.1-[Epsilon]. Interestingly, the families of graphs exhibited in Feige's work use the construction of Section 9 as a starting point. Even more conclusively, the results of Hastad [1996] and Feige and Kilian [1996] have shown that no polynomial time computable function approximates the clique number or chromatic number to within factors of [n.sup.1-[Epsilon], unless NP = RP. Thus no simple modification of the v function is likely to provide a much better approximation guarantee.

In related results, Alon and Kahale [1998] have also been able to use the semidefinite programming technique in conjunction with our techniques to obtain algorithms for computing bounds on the clique number of a graph with linear-sized cliques, improving upon some results due to Boppana and Halldorsson [1992]. Independent of our results, M. Szegedy (personal communication) has also shown that a similar construction yields graphs with vector chromatic number at most 3 that are not colorable using [n.sup.0.05] colors. Notice that the exponent obtained from his result is better than the one in Section 9. N. Alon (personal communication) has obtained a slight improvement over Szegedy's bound by using an interesting variant of the Kneser graph construction. Finally, the main algorithm presented here has been derandomized in a recent work of Mahajan and Ramesh [1995]. By combining our techniques with those of Blum [1994], Blum and Karger [1997] have given a 3-coloring algorithm with performance ratio O([n.sup.3/14]).

ACKNOWLEDGMENTS. Thanks to David Williamson for giving us a preview of the MAX-CUT result [Goemans and Williamson 1995] during a visit to Stanford. We are indebted to John Tukey and Jan Pedersen for their help in understanding multidimensional probability distributions. Thanks to David Williamson and Eva Tardos for discussions of the duality theory of SDP. We thank Noga Alon, Don Coppersmith, Jon Kleinberg, Laci Lovasz and Mario Szegedy for useful discussions, and the anonymous referees for the careful comments.

(1) Readers familiar with physics will see the connection to Maxwell's law on the distribution of velocities of molecules in [R.sup.3]. Maxwell started with the assumption that in every Cartesian coordinate system in [R.sup.3], the three components of the velocity vector are mutually independent and had expectation zero. Applying this assumption to rotations of the axes, we conclude that the velocity components must be independent normal variables with identical variance. This immediately implies Maxwell's distribution on the velocities.

REFERENCES

ALDOUS, D. 1989. Probability Approximations via the Poisson Clumping Heuristic. Springer-Verlag, New York.

ALIZADEH, F. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 1, 13-51.

ALON, N., AND KAHALE, N. 1994. A spectral technique for coloring random 3-colorable graphs. In Proceedings of the 26th ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 346-353.

ALON, N., AND KAHALE, N. 1998. Approximating the independence number via the Theta function. Math. Prog., in press.

ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1992. Proof verification and hardness of approximation problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 14-23.

BELLARE, M., AND SUDAN, M. 1994. Improved non-approximability results. In Proceedings of the 26th ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 184-193.

BERGE, C. 1973. Graphs and hypergraphs. North-Holland, Amsterdam, The Netherlands.

BLUM, A. 1994. New approximation algorithms for graph coloring. J. ACM 41 3 (May), 470-516.

BLUM, A., AND KARGER, D. 1997. Improved approximation for graph coloring. Inf. Proc. Lett. 61, 1 (Jan.), 49-53.

BOPPANA, R. B., AND HALLDORSSON, M. M. 1992. Approximating maximum independent sets by excluding subgraphs. BIT 32, 180-196.

BRIGGS, P., COOPER, K. D., KENNEDY, K., AND TORCZON, L. 1989. Coloring heuristics for register allocation. In Proceedings of the SIGPLAN 89 Conference on Programming Language Design and Implementation (Portland, Ore., June 21-23).

ACM, New York, pp. 275-284.

CHAITIN, G. J. 1982. Register allocation and spilling via graph coloring. In Proceedings of the SIGPLAN 89 Conference on Compiler Construction ACM, New York, pp. 98-101.

CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, P.W. 1981. Register allocation via coloring. Comput. Lang. 6, 47-57.

FELLER, W. 1968. An Introduction to Probability Theory and Its Applications. Wiley, New York.

FRANKL, P., AND RODL, V. 1994. Forbidden intersections. Trans. AMS. 300, 259-286.

FEIGE, U. 1995. Randomized graph products, chromatic numbers, and the Lovasz theta-function. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 635-640.

FEIGE, U., GOLDWASSER, S., LOVASZ, L., SAFRA, S., AND SZEGEDY, M. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2 (Mar.), 268-292.

FEIGE, U., AND KILIAN, J. 1996. Zero knowledge and chromatic number. In Proceedings of the 11th Annual Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., pp. 278-287.

FRIEZE, A., AND JERRUM, M. 1994. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Manuscript.

GAREY, M. R., AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York.

GOEMANS, M. X., AND WILLIAMSON, D.P. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6 (Nov.), 1115-1145.

GOLUB, G. H., AND VAN LOAN, C.F. 1983. Matrix Computations. Johns Hopkins University Press, Baltimore, Md.

GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its consequences in combinatorial optimization, combinatorica 1, 169-197.

GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1987. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.

HALLDORSSON, M. M. 1993. A still better performance guarantee for approximate graph coloring. Inf. Proc. Lett. 45, 19-23.

HASTAD, J. 1996. Clique is hard to approximate within [n.sup.1-[Epsilon]. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York.

JOHNSON, D. S. 1974. Worst case behavior of graph coloring algorithms. In Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium X, pp. 513-527.

KHANNA, S., LINIAL, N., AND SAFRA, S. 1992. On the hardness of approximating the chromatic number. In Proceedings of the 2nd Israeli Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 250-260.

KHANNA, S., MOTWANI, R., SUDAN, M., AND VAZIRANI, U. 1994. On syntactic versus computational views of approximability. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 819-830.

KNESER, M. 1955. Aufgabe 300. Jber. Deutsch. Math.-Verein. 58.

KNUTH, D. E. 1971. The Art of Computer Programming. Addison-Wesley, Reading, Mass.

KNUTH, D. E. 1994. The sandwich theorem. Elect. J. Combin. 1, 1-48.

LOVASZ, L. 1979. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1-7.

LUND, C., AND YANNAKAKIS, M. 1993. On the hardness of approximating minimization problems. In Proceedings of the 25th ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 286-293.

MAHAJAN, S., AND RAMESH, H. 1995. Derandomizing semidefinite programming based approximation algorithms. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 162-169.

MILNER, E. C. 1968. A combinatorial theorem on systems of sets. J. London Math. Soc. 43, 204-206.

MOTWANI, R., AND NAOR, J. 1993. On exact and approximate cut covers of graphs. Manuscript.

MOTWANI, R., AND RAGHAVAN, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, Mass.

RENYI, A. 1970. Probability Theory. Elsevier, New York.

SZEGEDY, M. 1994. A note on the [Theta] number of Lovasz and the generalized Delsarte bound. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 36-39.

WIGDERSON, A. 1983. Improving the performance guarantee for approximate graph coloring. J. ACM 30, 729-735.

WOOD, D. C. 1969. A technique for coloring a graph applicable to large-scale optimization problems. Comput. J. 12, 317.

RECEIVED AUGUST 1997; REVISED SEPTEMBER 1997; ACCEPTED NOVEMBER 1997

D. Karger was supported by a Hertz Foundation Graduate Fellowship; by National Science Foundation (NSF) Young Investigator Award CCR 93-57849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, Xerox Corporation; and by NSF Career Award CCR 96-24239.

R. Motwani was supported by an Alfred P. Sloan Research Fellowship; an IBM Faculty Development Award; and NSF Young Investigator Award CCR 93-57849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation.

The work of M. Sudan was done while he was at IBM Thomas J. Watson Research Center, Yorktown Heights, New York.

Authors' present addresses: D. Karger, MIT Laboratory for Computer Science, Cambridge, MA 02139, e-mail: karger@mit.edu, URL:http://theory.lcs.mit.edu/~karger; R. Motwani, Department of Computer Science, Stanford University, Stanford, CA 94305, e-mail: rajeev@cs.stanford.edu;

M. Sudan, MIT Laboratory for Computer Science, Cambridge, MA 02139, e-mail madhu@lcs.mit.edu.

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

[C] 1998 ACM 0004-5411/98/0300-0246 \$05.00
COPYRIGHT 1998 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.