Approximate graph coloring by semidefinite programming.
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(&Dgr;1/3 log1/2 &Dgr; log n), O(n1/4 log1/2 n)} colors where &Dgr; 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 &Dgr;. This result can be generalized to k-colorable graphs to obtain a coloring using  min{O(&Dgr;1-2/k log1/2 &Dgr; log n), O(n13/(k+1) log1/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 Lovsz &thgr;-function. We show lower bounds on the gap between the optimum solution of our semidefinite  program and the actual chromatic by duality this also demonstrates interesting new facts about the &thgr;-function.
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 -(G). Determining the
chromatic number of a graph is known to be NP-hard (cf. [20]).
Besides its theoretical significance as a canonical NP-hard problem, graph coloring arises naturally
in a variety of applications such as register allocation [11, 12, 13] and timetable/examination
scheduling [8, 43]. In many applications which 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 [27] who shows
that a version of the greedy algorithm gives an O(n= log n)-approximation algorithm for k-coloring.
improved this bound by giving an elegant algorithm which uses O(n 1\Gamma1=(k\Gamma1) ) colors
to legally color a k-colorable graph. Subsequently, other polynomial time algorithms were provided
by Blum [9] which use O(n 3=8 log 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 1\Gamma1=(k\Gamma4=3) log 8=5 n) colors. The best
known performance guarantee for general graphs is due to Halld'orsson [25] who provided a polynomial
time algorithm using a number of colors which is within a factor of O(n(log log 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 [34] used the results of Arora,
Lund, Motwani, Sudan, and Szegedy [6] and Feige, Goldwasser, Lov'asz, Safra, and Szegedy [17]
to show that there exists a (small) constant ffl ? 0 such that no polynomial time algorithm can
approximate the chromatic number of a graph to within a ratio of n ffl unless NP. The current
hardness result for the approximation of the chromatic number is due to Feige and Kilian [18] and
H-astad [26], who show that approximating it to within n 1\Gammaffi , for any ffi ? 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, Linial, and Safra [28] who show that it is not possible to color a 3-colorable graph with 4
colors in polynomial time unless
In this paper we present improvements on the result of Blum. In particular, we provide a
randomized polynomial time algorithm which colors a 3-colorable graph of maximum degree \Delta
with log n); O(n 1=4 log 1=2 n)g colors; moreover, this can be generalized to k-
colorable graphs to obtain a coloring using O(\Delta 1\Gamma2=k log 1=2 \Delta log n) or O(n 1\Gamma3=(k+1) log 1=2 n) colors.
Besides giving the best known approximations in terms of n, our results are the first non-trivial
approximations given in terms of \Delta. Our results are based on the recent work of Goemans and
used an algorithm for semidefinite optimization problems (cf. [23, 2]) 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 [37] 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
our techniques also lead to improved approximations for the MAX k-CUT problem [19]. We
also establish a duality relationship between the value of the optimum solution to our semidefinite
program and the Lov'asz #-function [23, 24, 33]. We show lower bounds on the gap between the
optimum solution of our semidefinite program and the actual chromatic by duality this
also demonstrates interesting new facts about the #-function.
Alon and Kahale [4] 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 [19] 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 Lov'asz #-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.
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 [33, 23].
Definition 2.1 Given a graph E) on n vertices, and a real number k - 1, a vector k-coloring
of G is an assignment of unit vectors u i from the space ! n to each vertex , such that
for any two adjacent vertices i and j the dot product of their vectors satisfies the inequality
The definition of an orthonormal representation [33, 23] 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 pro-
gramming. The methods in this section closely mimic those of Goemans and Williamson [21].
To solve the problem, we need the following auxiliary definition.
Definition 3.1 Given a graph E) on n vertices, a matrix k-coloring of the graph is an
n \Theta n symmetric positive semidefinite matrix M , with m
We now observe that matrix and vector k-colorings are in fact equivalent (cf. [21]). Thus, to
solve the vector coloring relaxation it will suffice to find a matrix k-coloring.
Fact 3.1 A graph has a vector k-coloring if and only if it has matrix k-coloring. Moreover, a vector
ffl)-coloring can be constructed from a matrix k-coloring in time polynomial in n and log(1=ffl).
Note that an exact solution cannot be found, as some of the values in it may be irrational.
Proof: Given a vector k-coloring fv i g, the matrix k-coloring is defined 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 is the transpose of U ). The rows of U are vectors
that form a vector k-coloring of G.
An ffi-close approximation to the matrix U can be found in time polynomial in n and log(1=ffi)
can be found using the Incomplete Cholesky Decomposition [21, 22]. (Here by ffi-close we mean a
matrix U 0 such that U 0 U has L1 norm less than ffi .) This in turn gives a vector
coloring of the graph, provided ffi is chosen appropriately.
Lemma 3.2 If a graph G has a vector k-coloring then a vector ffl)-coloring of the graph can
be constructed in time polynomial in k, n, and log(1=ffl).
Proof: Our proof is similar to those of Lov'asz [33] and Goemans-Williamson [21]. We construct
a semidefinite optimization problem (SDP) whose optimum is \Gamma1=(k \Gamma 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 ff
is positive semidefinite
subject to
Consider a graph which has a vector (and matrix) k-coloring. This means there is a solution to the
above semidefinite program with 1). The ellipsoid method or other interior point based
methods [23, 2] can be employed to find a feasible solution where the value of the objective is at
most \Gamma1=(k \Gamma 1)+ ffi in time polynomial in n and log 1=ffi. This implies that for all fi; jg 2
at most which is at most \Gamma1=(k
Thus a matrix ffl)-coloring can be found in time polynomial in k, n and log(1=ffl). From the
matrix coloring, the vector coloring can be found in polynomial time as was noted in the previous
lemma
Relating 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 - n + 1, there exist k unit vectors in ! n
such that the dot product of any distinct pair is \Gamma1=(k \Gamma 1).
Proof: Clearly it suffices to prove the lemma for other values of n, we make the
coordinates of the vectors 0 in all but the first k \Gamma 1 coordinates.) We begin by proving the claim for
explicitly provide unit vectors v (k)
for j. The vector v (k)
k(k\Gamma1) in all coordinates except the ith coordinate. In the ith
coordinate v (k)
i is
. It is easy to verify that the vectors are unit length and that their dot
products are exactly \Gamma1
.
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
be a vector k-coloring of G and assume without loss of generality that
Associate with each neighbor j of i a vector v 0
obtained by projecting v j onto
coordinates 2 through n and then scaling it up so that v 0
j has unit length. It suffices to show that
for any two adjacent vertices j and j 0 in the neighborhood of i, hv 0
Observe first that the projection of v j onto the first coordinate is negative and has magnitude
at least 1=(k \Gamma 1). This implies that the scaling factor for v 0
j is at least k\Gamma1
. Thus,
A simple induction using the above lemma shows that any graph containing a 1)-clique is
not k-vector colorable. Thus the "vector chromatic number" lies between between the clique and
chromatic number. This also shows that the analysis of Lemma 4.1 is tight in that \Gamma1=(k \Gamma 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 ~
and an ~
O(n )-coloring.
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 the at least half it
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.1 If an algorithm A can k i -semicolor any i-vertex subgraph of graph G in randomized
polynomial time, where k i increases with i, then A can be used to O(k n log n)-color G. Furthermore,
if there exists ffl ? 0 such that for all i, k can be used to color G with O(k n ) colors.
Proof: We show how to construct a coloring algorithm A 0 to color any subgraph H of G. A 0
starts by using A to semicolor H . Let S be the subset of vertices which have not been assigned
a color by A. Observe that jSj - jV (H)j=2. A 0 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 i be the maximum number of colors used by A 0 to color any i-vertex subgraph. Then c i
satisfies the recurrence
It is easy to see that this any c i satisfying this recurrence, must satisfy c i - k i log i. In particular
this implies that c n - O(k n log n). Furthermore for the case where k the above recurrence
is satisfied only when c
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 O(\Delta log 3 2 )-semicoloring, and thus into an
log 3
log n)-coloring of G. Combining this method with a technique of Wigderson [42] yields an
O(n 0:386 )-coloring of G. The method is based on [21] 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 fv i g n
. Recall that the unit vectors v i and v j associated
with an adjacent pair of vertices i and j have a dot product of at most \Gamma1=2, implying that the
angle between the two vectors is at least 2-=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 fi; jg 2 E, we say that the hyperplane H cuts
the edge if it separates the vectors v i and v 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
. The following lemma is a restatement of Lemma 1.2 of Goemans-Williamson [21].
Lemma 6.1 (Goemans-Williamson [21]) Given two vectors at an angle of ', the probability
that they are separated by a random hyperplane is exactly '=-.
We conclude that give a vector 3-coloring, for any edge fi; jg 2 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
which 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) r ,
and the expected fraction of the edges not cut is also (1=3) r .
We claim that this gives us a good semicoloring algorithm for the graph G. Notice that r
hyperplanes can partition ! n into at most 2 r distinct regions. (For r - n this is tight since r
hyperplanes create exactly 2 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 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) r m, where m is the
number of edges in E.
Theorem 6.2 If a graph has a vector 3-coloring, then it has an O(\Delta log 3
2 )-semicoloring which can
be constructed from the vector 3-coloring in polynomial time with high probability.
Proof: We use the random hyperplane method just described. Fix \Deltae, and note
that As noted above, r hyperplanes chosen independently
at random will cut an edge with probability 1=9\Delta. Thus the expected number of edges which
are not cut is since the number of edges is at most n\Delta=2. By Markov's
inequality (cf. [38], page 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. Delete one endpoint of each such edge leaves a set of 3n=4 colored vertices
with no uncut edges-ie, a semicoloring.
Repeating the entire process t times means that we will find a O(\Delta log 3 2 )-semicoloring with
probability at least 1 \Gamma 1=2 t .
Noting that log 3 2 ! 0:631 and that \Delta - n, this theorem and Lemma 5.1 implies a semicoloring
using O(n 0:631 ) colors.
By varying the number of hyperplanes, we can arrange for a tradeoff 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 [42]. Fix a threshold
value ffi. If there exists a vertex of degree greater than ffi, 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 ffi at the cost of using at most 2n=ffi colors.
Thus, we can obtain a semicoloring using O(n=ffi colors. The optimum choice of ffi is around
0:613 , which implies a semicoloring using O(n 0:387 ) colors. This semicoloring can be used to legally
color G using O(n 0:387 ) colors by applying Lemma 5.1.
Corollary 6.3 A 3-colorable graph with n vertices can be colored using O(n 0:387 ) colors by a polynomial
time randomized algorithm.
The bound just described is (marginally) weaker than the guarantee of a O(n 0:375 ) coloring due
to Blum [9]. 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.2. A simple
application of Wigderson's technique to this algorithm yields our final coloring algorithm.
Lemma 7.1 For every integer function vector k-colorable graph with maximum degree
\Delta can be semi-colored with at most O(\Delta 1\Gamma2=k
\Delta) colors in probabilistic polynomial time.
As in the previous section, this has immediate consequences for approximate coloring.
Given a vector k-coloring, we show that it is possible to extract an independent set of size
\Delta)). If we assign one color to this set and recurse on the rest, we will end up
using
\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 0 vertices and m 0 edges such that E[n
\Delta)). It follows that with
a polynomial number of repeated trials, we have a high probability of choosing a subgraph with
\Delta)). Given such a graph, we can delete one endpoint of each edge,
leaving an independent set of size n
\Delta)), as desired.
We now give the details of the construction. Suppose we have a vector k-coloring assigning unit
vectors v i to the vertices. We fix a parameter 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 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 ! n .
7.1 Probability Distributions in ! n
Recall that the standard normal distribution has the density function
distribution function \Phi(x), mean 0, and variance 1. A random vector is said to
have the n-dimensional standard normal distribution if the components r 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 [14, v. II], Knuth [31, v. 2], and R'enyi [39] 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 R'enyi [39] (see
also Section III.4 of Feller [14, v. II]).
Theorem 7.2 (Theorem IV.16.3 [39]) Let n-dimensional vector.
The projections of r onto two lines ' 1 and ' 2 are independent (and normally distributed) if and
only if ' 1 and ' 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.3 Let u be any unit vector in ! n . Let be a random vector (of
i.i.d. standard normal variables). The projection of r along u, given by dot product hu; ri, 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. I.e.,
x
OE(y) dy:
We will need the following well-known bounds on the tail of the standard normal distribution. (See,
for instance, Lemma VII.2 of Feller [14, v. I].)
Lemma 7.4 For every x ? 0,
x
x
Proof: The proof is immediate from inspection of the following equations relating the three
quantities in the desired inequality to integrals involving OE(x), and the fact OE(x)=x is finite for
every x ? 0.
x
x
OE(y)
\Gammay 4
x
x
OE(y)
dy:
Readers familiar with physics will see the connection to Maxwell's law on the distribution of velocities of molecules
in ! 3 . Maxwell started with the assumption that in every Cartesian coordinate system in ! 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.
7.2 The Analysis
We are now ready to complete the specification of the coloring algorithm. Recall that our goal is
to repeatedly identify, color and delete large independent sets from the graph. We actually set an
easier intermediate goal: find an induced subgraph with a large number n 0 of edges and a number
vertices. Since each edge only covers 2 vertices, the induced subgraph has
vertices with no incident edges. These vertices form an independent set 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 edges. We show that for sufficiently larger we get an
independent set of size roughly n 0 . Intuitively, this is true for the following reason. Any particular
vertex has some particular probability landing 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 chosen is p, the
probability that both endpoints of an edge are chosen is roughly p 4 . It follows that we end up
capturing (in expectation) a set of pn vertices that contains (in expectation) only
edges in a degree-\Delta graph. In such a set, at least pn \Gamma p 4 \Deltan 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 4 \Deltan - pn, meaning p - \Delta \Gamma1=3 . Taking p much smaller only
decreases the size of the independent set, so it turns out that our best choice is to take
yielding an indpendent set of
Repeating this capture process many times therefore
achieves an ~
We now formalize this intuitive argument. The vector r will be a random n-dimensional vector.
We precisely compute the expectation of n 0 , the number of vertices captured, and the expectation
of m 0 , 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
for a certain constant a depending on the vector chromatic number. We also
show that N(ac) grows roughly as N(c) a 2
. (For the case of 3-coloring we have a = 2, and thus if
picking a sufficiently large c, we can find an independent set of size
N(c)). (In the following lemma, n 0 and m 0 are functions of c: we do not make this dependence
explicit.)
Lemma 7.5 Let a =
k\Gamma2 . Then for any c,
Proof: We first bound E [n 0 ] from below. Consider a particular vertex i with assigned vector
. The probability that it is in the selected set is just P
normally distributed and thus this probability is N(c). By linearity of expectations, the expected
number of selected vertices
Now we bound E [m 0 ] from above. Consider an edge with endpoint vectors v 1 and v 2 . The
probability that this edge is in the induced subgraph is the probability that both endpoints are
selected, which is
where the expression follows from Corollary 7.3 applied to the preceding probability expression.
We now observe that
It follows that the probability that both endpoints of an edge are selected is at most 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 0 ], is at most n\DeltaN (ac)=2.
Combining the previous arguments, we deduce that
We now determine the a c such that \DeltaN (ac) ! 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.4, we find that
N(c)
N(ac)
a
p'
(The last equation holds since a =
2.) Thus if we choose c so that 1 \Gamma 1=c 2 -pand e (a 2 \Gamma1)c 2 =2 - \Delta, then we get \DeltaN (ac) ! N(c). Both conditions are satisfied, for sufficiently
large \Delta, if we set
smaller values of \Delta we can use the greedy 1-coloring algorithm to get a color 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
ne \Gammac 2 =2
c
\Gammac 3
-\Omega /
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 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.6 For every integer function vector k-colorable graph on n vertices can
be semicolored with O(n 1\Gamma3=(k+1) log 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
n) in the graph. Assume, by induction on k, that there exists a constant c ? 0
s.t. we can find an independent set of size ci 3=(k 0 +1) =(log 1=2 i) in any k 0 -vector chromatic graph on
k. We now prove the inductive assertion for k.
If G has a vertex of degree greater than \Delta k (n), then we find
a large independent set in the neighborhood of G. By Lemma 4.3, the neighborhood is vector
Hence we can find in this neighborhood, an independent set of size at least
n). If G does not have a vertex of degree greater than
then by Lemma 7.1, we can find an independent set of size at least
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 1\Gamma3=(k+1) log 1=2 n) colors.
The semicolorings guaranteed by Lemmas 7.1 and 7.6 can be converted into colorings using
Lemma 5.1, yielding the following theorem.
Theorem 7.7 Any vector k-colorable graph on n nodes with maximum degree \Delta can be colored, in
probabilistic polynomial time, using minfO(\Delta 1\Gamma2=k
8 Duality Theory
The most intensively studied relaxation of a semidefinite programming formulation to date is the
Lov'asz #-function [23, 24, 33]. 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 # 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 which 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
#-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 E) on n vertices, a strict vector k-coloring of G is an
assignment of unit vectors u i from the space ! n to each vertex , such that for any two
adjacent vertices i and j the dot product of their vectors satisfies the equality
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.1 The strict vector chromatic number of G is equal to #(G).
Proof: The dual of our strict vector coloring semidefinite program is as follows (cf. [2]):
is positive semidefinite
subject to
By duality, the value of this SDP is \Gamma1=(k \Gamma 1) where k is the strict vector chromatic number. Our
goal is to prove As before, the fact that fp ij g is positive semidefinite means we can find
vectors v i such that The last constraint says that the vectors v form an orthogonal
labeling [24], i.e. that hv
2 E. We now claim that the above optimization problem
can be reformulated as follows:
over all orthogonal labelings fv i g. To see this, consider an orthogonal labeling and define
this is the value of the first constraint in the first formulation of the dual (that
is, the constraint is - 1) and of the denominator in the second formulation. Then in an optimum
solution to the first formulation, we must have since otherwise we can divide each v i by
- 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 fv i g for the second
feasible solution to the first formulation with the same value. Thus the
optima are equal. We now manipulate the second formulation.
min
It follows from the last equation that the vector chromatic number is
However, by the same argument as used to reformulate the dual, this is equal to problem of
maximizing
orthogonal labelings such that
1. This is simply Lov'asz's
formulation of the #-function [24, 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\Omega\Gamma23 can have bounded vector chromatic number. This implies
that our technique is tight in that it is not possible to guarantee a coloring with n o(1) colors on all
vector 3-colorable graphs.
Definition 9.1 The Kneser graph K(m; defined as follows: the vertices are all possible r-sets
from a universe of size m; and, the vertices v i and v j are adjacent if and only if the corresponding
r-sets satisfy t.
We will need following theorem of Milner [36] regarding intersecting hypergraphs. Recall that
a collection of sets is called an antichain if no set in the collection contains another.
Theorem 9.1 (Milner) Let S 1 ff be an antichain of sets from a universe of size m such
that, for all i and j,
Then, it must be the case that
Notice that using all q-sets, for 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.2 Let
r
\Delta denote the number of vertices of the graph K(m;
m=8, the graph K(m; colorable but has chromatic number at least n 0:0113 .
Proof: We prove a lower bound on the Kneser graph's chromatic number - by establishing an
upper bound on its independence number ff. It is easy to verify that the ff in Milner's theorem is
exactly the independence number of the Kneser graph. To bound - observe that
ff
r
large enough m.
In the above sequence, the fourth line uses the approximation
for every fi 2 (0; 1), where c fi is a constant depending only on fi. Using the inequality
r
we obtain m - lg n and thus
Finally, it remains to show that the vector chromatic number of this graph is 3. This follows by
associating with each vertex v i an m-dimensional vector obtained from the characteristic vector of
the set S i . In the characteristic vector, +1 represents an element present in S i and \Gamma1 represents
elements absent from S i . The vector associated with a vertex is the characteristic vector of S i
scaled down by a factor of
m to obtain a unit vector. Given vectors corresponding to sets S i
and S j , the dot product gets a contribution of \Gamma1=m for coordinates in S i \DeltaS j and +1=m for the
others. (Here A\DeltaB represents the symmetric difference of the two sets, i.e., the set of elements
which 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
This implies that the vector chromatic number is 3.
More refined calculations can be used to improve this bound somewhat.
Theorem 9.3 There exists a Kneser graph K(m; which is 3-vector colorable but has chromatic
number exceeding n 0:016101 , where
r
denotes the number of vertices in the graph. Further,
for large k, there exists a Kneser graph K(m; which is k-vector colorable but has chromatic
number exceeding n 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
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 which
minimizes the vector chromatic number can be found by differentiation and is
mt
Setting proves that the vector chromatic number is at most
At the same time, using Milner's Theorem proves that the exponent of the chromatic number is at
least
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 0:016101 . For large constant vector chromatic numbers,
the limiting value of the exponent of the chromatic number is roughly 0:0717845.
Conclusions
The Lov'asz 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 Lov'asz [33] (see Knuth [32] for a survey).
This led to the hope that the following question may have an affirmative answer. Do there exist ffl,
graph G on n vertices
Our work in this paper proves a weak but non-trivial upper bound on the the chromatic number of
G in terms of #(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 [16] has shown that
for every ffl ? 0, there exist families of graphs for which -(G) ? #(G)n 1\Gammaffl . Interestingly, families of
graphs exhibited in Feige's work use the construction of Section 9 as a starting point. Even more
conclusively, the results of H-astad [26] and Feige and Kilian [18] have shown that no polynomial
time computable function approximates the clique number or chromatic number to within factors
of n 1\Gammaffl , unless NP=RP. Thus no simple modification of the # function is likely to provide a much
better approximation guarantee.
In related results, Alon and Kahale [5] 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 [10]. Independent of our results, Szegedy [41] has also shown that a similar construction
yields graphs with vector chromatic number at most 3 but which are not colorable using n 0:05 colors.
Notice that the exponent obtained from his result is better than the one in Section 9. Alon [3] 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 [35].

Acknowledgments

Thanks to David Williamson for giving us a preview of the MAX-CUT result [21] during a visit to
Stanford. We are indebted to John Tukey and Jan Pedersen for their help in understanding multi-dimensional
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 Lov'asz
and Mario Szegedy for useful discussions, and the anonymous referees for the careful comments.



--R

Probability Approximations via the Poisson Clumping Heuristic.
Interior point methods in semidefinite programming with applications to combinatorial optimization.
Personal Communication
A spectral technique for coloring random 3-colorable graphs
Approximating the independence number via the Theta function.
Proof Verification and Hardness of Approximation Problems.
Improved Non-approximability Results

New approximation algorithms for graph coloring.
Approximating maximum independent sets by excluding subgraphs.
Coloring heuristics for register alloca- tion
Register allocation and spilling via graph coloring.
Register allocation via coloring.
An Introduction to Probability Theory and Its Applications.
Forbidden Intersections.
Randomized graph products
Interactive proofs and the hardness of approximating cliques.
Zero knowledge and chromatic number.
Improved approximation algorithms for MAX k-CUT and MAX BISECTION
Computers and Intractability: A Guide to the Theory of NP-Completeness
Improved approximation algorithms for maximum cut and satisfiability problems.
Matrix Computations.
The ellipsoid method and its consequences in combinatorial optimization.
Geometric Algorithms and Combinatorial Optimization.
A still better performance guarantee for approximate graph coloring.
Clique is hard to approximate within n 1
Worst case behavior of graph coloring algorithms.
On the Hardness of Approximating the Chromatic Number.
On Syntactic versus Computational Views of Approximability.
Aufgabe 300.
The Art of Computer Programming.
The Sandwich Theorem.
On the Shannon capacity of a graph.
On the hardness of approximating minimization problems.
Derandomizing semidefinite programming based approximation algorithms.
A combinatorial theorem on systems of sets.
On Exact and Approximate Cut Covers of Graphs.
Randomized Algorithms.
Probability Theory.
A note on the ' number of Lov'asz and the generalized Delsarte bound.
Personal Communication.
Improving the Performance Guarantee for Approximate Graph Coloring.
A Technique for Coloring a Graph Applicable to Large-Scale Optimization Prob- lems
--TR
Improving the performance guarantee for approximate graph coloring
Coloring heuristics for register allocation
A still better performance guarantee for approximate graph coloring
On the hardness of approximating minimization problems
Approximating maximum independent sets by excluding subgraphs
New approximation algorithms for graph coloring
Improved non-approximability results
A spectral technique for coloring random 3-colorable graphs (preliminary version)
Randomized algorithms
Randomized graph products, chromatic numbers, and Lovasz j-function
Interactive proofs and the hardness of approximating cliques
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
An MYAMPERSANDOtilde;(<italic>n</italic><supscrpt>3/14</supscrpt>)-coloring algorithm for 3-colorable graphs
Computers and Intractability
The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information
Zero Knowledge and the Chromatic Number
Derandomizing semidefinite programming based approximation algorithms
Register allocation MYAMPERSANDamp; spilling via graph coloring
Clique is hard to approximate within n1-

--CTR
Yonatan Bilu, Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number, Journal of Combinatorial Theory Series B, v.96 n.4, p.608-613, July 2006
Eran Halperin , Ram Nathaniel , Uri Zwick, Coloring k-colorable graphs using relatively small palettes, Journal of Algorithms, v.45 n.1, p.72-90, October 2002
Robert A. Stubbs , Sanjay Mehrotra, Generating Convex Polynomial Inequalities for Mixed 01 Programs, Journal of Global Optimization, v.24 n.3, p.311-332, November 2002
Eran Halperin , Ram Nathaniel , Uri Zwick, Coloring
Amin Coja-Oghlan , Lars Kuhtz, An improved algorithm for approximating the chromatic number of G
Michael Krivelevich , Ram Nathaniel , Benny Sudakov, Approximating coloring and maximum independent sets in 3-uniform hypergraphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.327-328, January 07-09, 2001, Washington, D.C., United States
Uriel Feige , Michael Langberg, The RPR2 rounding technique for semidefinite programs, Journal of Algorithms, v.60 n.1, p.1-23, July 2006
Sanjeev Arora , Eden Chlamtac, New approximation guarantee for chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Michel X. Goemans , David Williamson, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.443-452, July 2001, Hersonissos, Greece
Irit Dinur , Elchanan Mossel , Oded Regev, Conditional hardness for approximate coloring, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Miroslav Chlebk , Janka Chlebkov, Complexity of approximating bounded variants of optimization problems, Theoretical Computer Science, v.354 n.3, p.320-338, 4 April 2006
Amin Coja-Oghlan, Solving NP-hard semirandom graph problems in polynomial expected time, Journal of Algorithms, v.62 n.1, p.19-46, January, 2007
Michel X. Goemans , David P. Williamson, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Journal of Computer and System Sciences, v.68 n.2, p.442-470, March 2004
Moses Charikar, On semidefinite programming relaxations for graph coloring and vertex cover, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.616-620, January 06-08, 2002, San Francisco, California
D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Alon , Konstantin Makarychev , Yury Makarychev , Assaf Naor, Quadratic forms on graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Bernard Chazelle , Carl Kingsford , Mona Singh, The side-chain positioning problem: a semidefinite programming formulation with new rounding schemes, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.86-94, June 08-08, 2003, San Diego, California, USA
Arash Behzad , Izhak Rubin, Multiple Access Protocol for Power-Controlled Wireless Access Nets, IEEE Transactions on Mobile Computing, v.3 n.4, p.307-316, October 2004
Amin Coja-Oghlan, Finding Large Independent Sets in Polynomial Expected Time, Combinatorics, Probability and Computing, v.15 n.5, p.731-751, September 2006
Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece
Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA
Per Austrin, Balanced max 2-sat might not be the hardest, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Ccile Murat , Vangelis Th. Paschos, On the probabilistic minimum coloring and minimum k-coloring, Discrete Applied Mathematics, v.154 n.3, p.564-586, 1 March 2006
Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001
Bernard Chazelle , Carl Kingsford , Mona Singh, A Semidefinite Programming Approach to Side Chain Positioning with New Rounding Strategies, INFORMS Journal on Computing, v.16 n.4, p.380-392, Fall 2004
Amin Coja-oghlan, The Lovsz Number of Random Graphs, Combinatorics, Probability and Computing, v.14 n.4, p.439-465, July 2005
V. Th. Paschos, Polynomial approximation and graph-coloring, Computing, v.70 n.1, p.41-86, March
approximation algorithms;randomized algorithms;NP-completeness;graph coloring;chromatic number