A Spectral Technique for Coloring Random 3-Colorable Graphs.
Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3  with high probability, whenever p $\geq$ c/n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p $\geq$ polylog(n)/n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.
Introduction
A vertex coloring of a graph G is proper if no adjacent vertices receive the same color. The chromatic
number -(G) of G is the minimum number of colors in a proper vertex coloring of it. The problem
of determining or estimating this parameter has received a considerable amount of attention in
Combinatorics and in Theoretical Computer Science, as several scheduling problems are naturally
formulated as graph coloring problems. It is well known (see [13, 12]) that the problem of properly
coloring a graph of chromatic number k with k colors is NP-hard, even for any fixed k - 3, and it is
therefore unlikely that there are efficient algorithms for optimally coloring an arbitrary 3-chromatic
input graph.
On the other hand, various researchers noticed that random k-colorable graphs are usually easy
to color optimally. Polynomial time algorithms that optimally color random k-colorable graphs for
every fixed k with high probability, have been developed by Kucera [15], by Turner [18] and by
Dyer and Frieze [8], where the last paper provides an algorithm whose average running time over
all k-colorable graphs on n vertices is polynomial. Note, however, that most k-colorable graphs
are quite dense, and hence easy to color. In fact, in a typical k-colorable graph, the number of
common neighbors of any pair of vertices with the same color exceeds considerably that of any
pair of vertices of distinct colors, and hence a simple coloring algorithm based on this fact already
works with high probability. It is more difficult to color sparser random k-colorable graphs. A
A preliminary version of this paper appeared in the Proc. of the 26 th ACM STOC, ACM Press (1994), 346-355.
Institute for Advanced Study, Princeton, NJ 08540, USA and Department of Mathematics, Tel Aviv University,
Tel Aviv, Israel. Email: noga@math.tau.ac.il. Research supported in part by the Sloan Foundation, Grant No. 93-6-6
and by a USA-Israel BSF grant.
y ATT Bell Laboratories, Murray Hill, NJ 07974. Email: kahale@research.att.com. This work was done while the
author was at DIMACS.
precise model for generating sparse random k-colorable graphs is described in the next subsection,
where the sparsity is governed by a parameter p that specifies the edge probability. Petford and
Welsh [16] suggested a randomized heuristic for 3-coloring random 3-colorable graphs and supplied
experimental evidence that it works for most edge probabilities. Blum and Spencer [6] (see also
[3] for some related results) designed a polynomial algorithm and proved that it colors optimally,
with high probability, random 3-colorable graphs on n vertices with edge probability p provided
arbitrarily small but fixed ffl ? 0. Their algorithm is based on a path counting
technique, and can be viewed as a natural generalization of the simple algorithm based on counting
common neighbors (that counts paths of length 2), mentioned above.
Our main result here is a polynomial time algorithm that works for sparser random 3-colorable
graphs. If the edge probability p satisfies p - c=n, where c is a sufficiently large absolute constant,
the algorithm colors optimally the corresponding random 3-colorable graph with high probability.
This settles a problem of Blum and Spencer [6], who asked if one can design an algorithm that works
almost surely for p - polylog(n)=n. (Here, and in what follows, almost surely always means: with
probability that approaches 1 as n tends to infinity). The algorithm uses the spectral properties
of the graph and is based on the fact that almost surely a rather accurate approximation of the
color classes can be read from the eigenvectors corresponding to the smallest two eigenvalues of the
adjacency matrix of a large subgraph. This approximation can then be improved to yield a proper
coloring.
The algorithm can be easily extended to the case of k-colorable graphs, for any fixed k, and to
various models of random regular 3-colorable graphs.
We implemented our algorithm and tested it for hundreds of graphs drawn at random from
the distribution of G 3n;p;3 . Experiments show that our algorithm performs very well in practice.
The running time is a few minutes on graphs with up to 100000 nodes, and the range of edge
probabilities on which the algorithm is successful is in fact even larger than what our analysis
predicts.
1.1 The model
There are several possible models for random k-colorable graphs. See [8] for some of these models
and the relation between them. Our results hold for most of these models, but it is convenient to
focus on one, which will simplify the presentation. Let V be a fixed set of kn labelled vertices. For a
real kn;p;k be the random graph on the set of vertices V obtained as follows; first, split
the vertices of V arbitrarily into k color classes W each of cardinality n. Next, for each u
and v that lie in distinct color classes, choose uv to be an edge, randomly and independently, with
probability p. The input to our algorithm is a graph G kn;p;k obtained as above, and the algorithm
succeeds to color it if it finds a proper k coloring. Here we are interested in fixed k - 3 and large
n. We say that an algorithm colors G kn;p;k almost surely if the probability that a randomly chosen
graph as above is properly colored by the algorithm tends to one as n tends to infinity. Note
that we consider here deterministic algorithms, and the above statement means that the algorithm
succeeds to color almost all random graphs generated as above.
A closely related model to the one given above is the model in which we do not insist that the
color classes have equal sizes. In this model one first splits the set of vertices into k disjoint color
classes by letting each vertex choose its color randomly, independently and uniformly among the
possibilities. Next, one chooses every pair of vertices of distinct color classes to be an edge with
probability p. All our results hold for both models, and we focus on the first one as it is more
convenient. To simplify the presentation, we restrict our attention to the case
graphs, since the results for this case easily extend to every fixed k. In addition, we make no attempt
to optimize the constants and assume, whenever this is needed, that c is a sufficiently large contant,
and the number of vertices 3n is sufficiently large.
1.2 The algorithm
Here is a description of the algorithm, which consists of three phases. Given a graph
E), define be the graph obtained from G by deleting all edges incident
to a vertex of degree greater than 5d. Denote by A the adjacency matrix of G 0 , i.e., the 3n by
3n matrix (a uv ) u;v2V defined by a It is well known
that since A is symmetric it has real eigenvalues - 1 and an orthonormal basis
of eigenvectors e 1 . The crucial point is that almost surely one can
deduce a good approximation of the coloring of G from e 3n\Gamma1 and e 3n . Note that there are several
efficient algorithms to compute the eigenvalues and the eigenvectors of symmetric matrices (cf.,
e.g., [17]) and hence e 3n\Gamma1 and e 3n can certainly be calculated in polynomial time. For the rest of
the algorithm, we will deal with G rather than G 0 .
Let t be a non-zero linear combination of e 3n\Gamma1 and e 3n whose median is zero, that is, the
number of positive components of t as well as the number of its negative components are both at
most 3n=2. (It is easy to see that such a combination always exists and can be found efficiently.)
Suppose also that t is normalized so that it's l 2 -norm is
2n.
1=2g. This is an approximation for the
coloring, which will be improved in the second phase by iterations, and then in the third phase to
obtain a proper 3-coloring.
In iteration i of the second phase, ne, construct the color classes V i
3 as follows. For every vertex v of G, let N(v) denote the set of all its neighbors in G. In the
i-th iteration, color v by the least popular color of its neighbors in the previous iteration. That is,
put v in V i
is the minimum among the three quantities
l
where equalities are broken arbitrarily. We will show that the three sets V q
correctly color all but
vertices.
The third phase consists of two stages. First, repeatedly uncolor every vertex colored j that has
less than d=2 neighbors (in G) colored l, for some l 2 f1; 2; 3g \Gamma fjg. Then, if the graph induced on
the set of uncolored vertices has a connected component of size larger than log 3 n, the algorithm
fails. Otherwise, find a coloring of every component consistent with the rest of the graph using
brute force exhaustive search. If the algorithm cannot find such a coloring, it fails.
Our main result is the following.
Theorem 1.1 If p ? c=n, where c is a sufficiently large constant, the algorithm produces a proper
3-coloring of G with probability
The intuition behind the algorithm is as follows. Suppose every vertex in G had exactly d neighbors
in every color class other than its own. Then G G. Let F be the 2-dimensional subspace of all
vectors are constant on every color class, and whose sum is 0. A simple
calculation (as observed in [1]) shows that any non-zero element of F is an eigenvector of A with
eigenvalue \Gammad. Moreover, if E is the union of random matchings, one can show that \Gammad is almost
surely the smallest eigenvalue of A and that F is precisely the eigenspace corresponding to \Gammad.
Thus, any linear combination t of e 3n\Gamma1 and e 3n is constant on every color class. If the median of
t is 0 and its l 2 -norm is
2n, then t takes the values 0, 1 or \Gamma1 depending on the color class, and
the coloring obtained after phase 1 of the algorithm is a proper coloring. In the model specified in
Subsection 1.1 these regularity assumptions do not hold, but every vertex has the same expected
number of neighbors in every color class other than its own. This is why phase 1 gives only an
approximation of the coloring and phases 2 and 3 are needed to get a proper coloring.
We prove Theorem 1.1 in the next two sections. We use the fact that almost surely the largest
eigenvalue of G 0 is at least (1 \Gamma 2 \Gamma\Omega\Gamma d) )2d, and that its two smallest eigenvalues are at most \Gamma(1 \Gamma
d) )d and all other eigenvalues are in absolute value O(
d). The proof of this result is based
on a proper modification of techniques developed by Friedman, Kahn and Szemer'edi in [11], and
is deferred to Section 3. We show in Section 2 that it implies that each of the two eigenvectors
corresponding to the two smallest eigenvalues is close to a vector which is a constant on every color
class, where the sum of these three constants is zero. This suffices to show that the sets V 0
reasonably good approximation to the coloring of G, with high probability.
Theorem 1.1 can then be proved by applying the expansion properties of the graph G (that
hold almost surely) to show that the iteration process above converges quickly to a proper coloring
of a predefined large subgraph H of G. The uncoloring procedure will uncolor all vertices which
are wrongly colored, but will not affect the subgraph H . We then conclude by showing that the
largest connected component of the induced subgraph of G on V \Gamma H is of logarithmic size almost
surely, thereby showing that the brute-force search on the set of uncolored vertices terminates in
polynomial time. We present our implementation results in Section 4. Section 5 contains some
concluding remarks together with possible extensions and results for related models of random
graphs.
2 The proof of the main result
E) be a random 3-colorable graph generated according to the model described
above. Denote by W 1 3 the three color classes of vertices of G. Let G 0 be the graph
obtained from G by deleting all edges adjacent to vertices of degree greater than 5d, and let A
be the adjacency matrix of G 0 . Denote by - the eigenvalues of A, and by
3n the corresponding eigenvectors, chosen so that they form an orthonormal basis of
R 3n .
In this section we first show that the approximate coloring produced by the algorithm using the
eigenvectors e 3n\Gamma1 and e 3n is rather accurate almost surely. Then we exhibit a large subgraph H
and show that, almost surely, the iterative procedure for improving the coloring colors H correctly.
We then show that the third phase finds a proper coloring of G in polynomial time, almost surely.
We use the following statement, whose proof is relegated to Section 3.
Proposition 2.1 In the above notation, almost surely,
d) )d and
d) for all 2.
Remark. One can show that, when 2.1 would not hold if we were
dealing with the spectrum of G rather than that of G 0 , since the graph G is likely to contain many
vertices of degree ?? d, and in this case the assertion of (iii) does not hold for the eigenvalues of
G.
2.1 The properties of the last two eigenvectors
We show in this subsection that the eigenvectors e 3n\Gamma1 and e 3n are almost constant on every color
class. For this, we exhibit two orthogonal vectors constant on every color class which, roughly
speaking, are close to being eigenvectors corresponding to \Gammad. Let be the vector
defined by x be the vector defined
by y We denote by jjf jj the l 2 -norm of a
vector f .
Lemma 2.2 Almost surely there are two vectors
are both linear combinations of e
and e 3n .
Proof. We use the following lemma, whose proof is given below.
Lemma 2.3 Almost surely:
We prove the existence of ffi as above. The proof of the existence of ffl is analogous. Let
We show that the coefficients c are small compared to jjyjj. Indeed,
3n
where the last inequality follows from parts (i) and (iii) of Proposition 2.1. Define
By (1) and Lemma 2.3 it follows that jjffijj
O(n=d). on the other hand, y \Gamma ffi is a
linear combination of e 3n\Gamma1 and e 3n . 2
Note that it was crucial to the proof of Lemma 2.2 that, almost surely,
rather
as is the case for some vectors in f\Gamma1; 0; 1g 3n .
Proof of Lemma 2.3 To prove the first bound, observe that it suffices to show that the sum
of squares of the coordinates of dI)y on W 1 is O(nd) almost surely, as the sums on W 2 and
W 3 can be bounded similarly. The expectation of the vector dI)y is the null vector, and the
expectation of the square of each coordinate of dI)y is O(d), by a standard calculation. This
is because each coordinate of dI)y is the sum of n independent random variables, each with
mean 0 and variance O(d=n). This implies that the expected value of the sum of squares of the
coordinates of dI)y on W 1 is O(nd). Similarly, the expectation of the fourth power of each
coordinate of dI)y is O(d 2 ). Hence, the variance of the square of each coordinate is O(d 2 ).
However, the coordinates of dI)y on W 1 are independent random variables, and hence the
variance of the sum of the squares of the W 1 coordinates is equal to the sum of the variances, which
is O(nd 2 ). The first bound can now be deduced from Chebyshev's Inequality. The second bound
can be shown in a similar manner. We omit the details. 2
The vectors are independent since they are nearly orthogonal. Indeed, if
O
n=d
Thus
Therefore, by the above lemma, the two vectors
3ne
3ne 3n can be written as linear
combinations of x \Gamma ffl and y \Gamma ffi. Moreover, the coefficients in these linear combinations are all
O(1) in absolute value. This is because are nearly orthogonal, and the l 2 -norm
of each of the four vectors
3ne
3ne 3n is \Theta( p
n). More precisely, if one of
the vectors
3ne
3ne 3n is written as by the triangle inequality,
n) which, by a calculation similar to the one above, implies
that thus ff and fi are O(1). on the other hand, the
coefficients of the vector t defined in subsection 1.2 along the vectors e 3n\Gamma1 and e 3n are at most
2n. It follows that the vector t defined in the algorithm is also a linear combination of the
vectors coefficients whose absolute values are both O(1). Since both x and y
belong to the vector space F defined in the proof of Proposition 2.1, this implies that
be the value of f on W i , for 1 - i - 3. Assume without
loss of generality that ff 1 - ff 2 - ff 3 . Since jjjjj O(n=d), at most O(n=d) of the coordinates of
are greater than 0:01 in absolute value. This implies that jff 2 j - 1=4, because otherwise at least
O(n=d) coordinates of t would have the same sign, contradicting the fact that 0 is a median
of t. As ff 1
implies that ff 1 ? 3=4
and ff 3 ! \Gamma3=4. Therefore, the coloring defined by the sets V 0
agrees with the original coloring of
G on all but at most O(n=d) ! 0:001n coordinates.
2.2 The iterative procedure
Denote by H the subset of V obtained as follows. First, set H to be the set of vertices having at
most 1:01d neighbors in G in each color class. Then, repeatedly, delete any vertex in H having less
than 0:99d neighbors in H in some color class (other than its own.) Thus, each vertex in H has
roughly d neighbors in H in each color class other than its own.
Proposition 2.4 Almost surely, by the end of the second phase of the algorithm, all vertices in H
are properly colored.
To prove Proposition 2.4, we need the following lemma.
Lemma 2.5 Almost surely, there are no two subsets of vertices U and W of V such that jU j -
0:001n, and every vertex v of W has at least d=4 neighbors in U .
Proof. Note that if there are such two (not necessarily disjoint) subsets U and W , then the number
of edges joining vertices of U and W is at least djW j=8. Therefore, by a standard calculation, the
probability that there exist such two subsets is at most
3n
!/
3n
!/
di=8
d) ):If a vertex in H is colored incorrectly at the end of iteration i of the algorithm in phase 2 (i.e.
if it is colored j and does not belong to W j ), it must have more than d=4 neighbors in H colored
incorrectly at the end of iteration To see this, observe that any vertex of H has at most
neighbors outside H , and hence if it has at most d=4 wrongly colored
neighbors in H , it must have at least 0:99d \Gamma d=4 ? d=2 neighbors of each color other than its
correct color and at most d=4 0:04d neighbors of its correct color. By repeatedly applying the
property asserted by the above lemma with U being the set of vertices of H whose colors in the
end of the iteration are incorrect, we deduce that the number of incorrectly colored vertices
decreases by a factor of two (at least) in each iteration, implying that all vertices of H will be
correctly colored after dlog 2 ne iterations. This completes the proof of Proposition 2.4. We note
that by being more careful one can show that O(log d n) iterations suffice here, but since this only
slightly decreases the running time we do not prove the stronger statement here. 2
A standard probabilistic argument based on the Chernoff bound (see, for example, [2, Appendix
A]) shows that almost surely if p - fi log n=n, where fi is a suitably large constant. Thus,
it follows from Proposition 2.4 that the algorithm almost surely properly colors the graph by the
end of Phase 2 if p - fi log n=n.
For two sets of vertices X and Z, let e(X; Z) denote the number of edges (u; v) 2 E, with
and v 2 Z.
Lemma 2.6 There exists a constant fl ? 0 such that almost surely the following holds.
(i) For any two distinct color classes V 1 and V 2 , and any subset X of V 1 and any subset Y of V 2 ,
(ii) If J is the set of vertices having more than 1:01d neighbors in G in some color class, then
Proof For any subset X of is the sum of independent Bernoulli variables. By
standard Chernoff bounds, the probability that there exist two color classes V 1 and V 2 , a subset X
of V 1 and a subset Y of V 2 such that jX
is at most/
ffln
Therefore, (i) holds almost surely if fl is a sufficiently small constant. A similar reasoning applies
to (ii). Therefore, both (i) and (ii) hold if fl is a sufficiently small constant. 2
Lemma 2.7 Almost surely, H has at least (1 \Gamma 2 \Gamma\Omega\Gamma d) )n vertices in every color class.
Proof. It suffices to show that there are at most 7 \Delta 2 \Gammafl d n vertices outside H . Assume for
contradiction that this is not true. Recall that H is obtained by first deleting all the vertices in
J , and then by a deletion process in which vertices with less than 0:99d neighbors in the other
color classes of H are deleted repeatedly. By Lemma 2.6 jJ almost surely, and so at
least 6 \Delta 2 \Gammafl d n vertices have been deleted because they had less than 0:99d neighbors in H in some
color class (other than their own.) Consider the first time during the deletion process where there
exists a subset X of a color class V i of cardinality 2 \Gammafl d n, and a j 2 f1; 2; 3g \Gamma fig such that every
vertex of X has been deleted because it had less than 0:99d neighbors in the remaining subset of
Y be the set of vertices of V j deleted so far. Then jY j. Note that every
vertex in X has less than 0:99d neighbors in We therefore get a contradiction by applying
Lemma 2.6 to (X; Y ). 2
2.3 The third phase
We need the following lemma, which is an immediate consequence of Lemma 2.5.
Lemma 2.8 Almost surely, there exists no subset U of V of size at most 0:001n such that the
graph induced on U has minimum degree at least d=2.
Lemma 2.9 Almost surely, by the end of the uncoloring procedure in Phase 3 of the algorithm, all
vertices of H remain colored, and all colored vertices are properly colored, i.e. any vertex colored i
belongs to W i . (We assume, of course, that the numbering of the colors is chosen appropriately).
Proof. By Proposition 2.4 almost surely all vertices of H are properly colored by the end of
Phase 2. Since every vertex of H has at least 0:99d neighbors (in H) in each color class other
than its own, all vertices of H remain colored. Moreover, if a vertex is wrongly colored at the
end of the uncoloring procedure, then it has at least d=2 wrongly colored neighbors. Assume for
contradiction that there exists a wrongly colored vertex at the end of the uncoloring procedure.
Then the subgraph induced on the set of wrongly colored vertices has minimum degree at least
d=2, and hence it must have at least 0:001n vertices by Lemma 2.8. But, since it does not intersect
H , it has at most 2 \Gamma\Omega\Gamma d) n vertices by Lemma 2.7, leading to a contradiction. 2
In order to complete the proof of correctness of the algorithm, it remains to show that almost
surely every connected component of the graph induced on the set of uncolored vertices is of size
at most log 3 n. We prove this fact in the rest of this section. We note that it is easy to replace
the term log 3 n by O( log 3 n
d ), but for our purposes the above estimate suffices. Note also that if
some of these components are actually components of the original graph G, as for
such value of p the graph G is almost surely disconnected (and has many isolated vertices).
Lemma 2.10 Let K be a graph, partition of the vertices of K into three disjoint
subsets, i an integer, and L the set of vertices of K that remain after repeatedly deleting the
vertices having less than i neighbors in V 1 , V 2 or V 3 . Then the set L does not depend on the order
in which vertices are deleted.
Proof Let L be the set of vertices that remain after a deletion process according to a given order.
Consider a deletion process according to a different order. Since every vertex in L has at least
neighbors in no vertex in L will be deleted in the second deletion
process (otherwise, we get a contradiction by considering the first vertex in L deleted.) Therefore,
the set of vertices that remain after the second deletion process contains L, and thus equals L by
symmetry. 2
Lemma 2.10 implies that H does not depend on the order in which vertices are deleted.
Proposition 2.11 Almost surely the largest connected component of the graph induced on
has at most log 3 n vertices.
Proof. Let T be a fixed tree on log 3 n vertices of V all of whose edges have their two endpoints
in distinct color classes W i , Our objective is to estimate the probability that G
contains T as a subgraph that does not intersect H , and show that this probability is sufficiently
small to ensure that almost surely the above will not occur for any T . This property would certainly
hold were a random subset of V of cardinality 2 \Gamma\Omega\Gamma d) n. Indeed, if this were the case, the
probability that G contains T as a subgraph that does not intersect H would be upper bounded
by the probability 2 \Gamma\Omega\Gamma djT that T is a subset of times the probability (d=n) jT j\Gamma1 that T is
a subgraph of G. This bound is sufficiently small for our needs. Although H is not a random
subset of V , we will be able to show a similar bound on the probability that G contains T as a
subgraph that does not intersect H . To simplify the notation, we let T denote the set of edges of
the tree. Let V (T ) be the set of vertices of T , and let I be the subset of all vertices
degree in T is at most 4. Since T contains jV be the subset
of V obtained by the following procedure, which resembles that of producing H (but depends on
to be the set of vertices having at most 1:01d \Gamma 4 neighbors in G in each
color class V i . Then delete from H 0 all vertices of V (T repeatedly, delete any vertex in
having less than 0:99d neighbors in H 0 in some color class (other than its own.)
Lemma 2.12 Let F be a set of edges, each having endpoints in distinct color classes W i , W j . Let
be the set obtained by replacing E by F [T in our definition of H, and H 0 be the set
obtained by replacing E by F in our definition of H 0 . Then H
Proof. First, we show that the initial value of H 0 obtained after deleting the vertices
with more than 1:01d \Gamma 4 neighbors in a color class of G and after deleting the vertices in V (T
is a subset of the initial value of H(F [T ). Indeed, let v be any vertex that does not belong to the
initial value of H(F [ T ), i.e. v has more than 1:01d neighbors in some color class of (V; F [ T ).
We distinguish two cases:
1. I . In this case, v does not belong to the initial value of H 0
2. I . Then v is incident with at most 4 edges of T , and so it has more than 1:01d \Gamma 4
neighbors in some color class in (V; F ).
In both cases, v does not belong to the initial value of H 0 This implies the assertion of the
lemma, since the initial value of H 0 subgraph of the initial value of H(F [ T ) and hence,
by Lemma 2.10, any vertex which will be deleted in the deletion process for constructing H will be
deleted in the corresponding deletion process for producing H 0 as well. 2
Lemma 2.13
Pr [T is a subgraph of G and V (T is a subgraph of G] Pr
Proof. It suffices to show that
is a subgraph of G] - Pr
But, by Lemma 2.12,
F :I"H(F[T)=;
Pr

Pr
is a subgraph of G

is a subgraph of G];
where F ranges over the sets of edges with endpoints in different color classes, and F 0 ranges
over those sets that do not intersect T . The third equation follows by regrouping the edge-sets
F according to F noting (the obvious fact) that, for a given set F 0 that does
not intersect T , the probability that F such that is equal to
The fourth equation follows from the independence of the events
F 0 and T is a subgraph of G. 2
Returning to the proof of Proposition 2.11 we first note that we can assume without loss of
generality that d - fi log n, for some constant fi ? 0 (otherwise .) If this inequality holds
by modifying the arguments in the proof of Lemma 2.7, one can show that each of the graphs
(corresponding to the various choices of V (T at most 2
d) n vertices in each color
class, with probability at least 1 \Gamma 2 \Gamman \Theta(1)
. Since the distribution of H 0 depends only on V (T
(assuming the W i 's are fixed), it is not difficult to show that this implies that Pr [I " H
at most 2
\Gamma\Omega\Gamma djIj) . Since jI j - jV (T )j=2 and since the probability that T is a subgraph of G is
precisely (d=n) jV (T )j\Gamma1 we conclude, by Lemma 2.13, that the probability that there exists some T
of size log 3 n which is a connected component of the induced subgraph of G on H is at most\Gamma\Omega\Gamma d log 3 n) (d=n) log 3 multiplied by the number of possible trees of this size, which is
3n
log 3 n
(log 3 n) log 3
Therefore, the required probability is bounded by
3n
log 3 n
(log 3 n) log 3 n\Gamma2 2 \Gamma\Omega\Gamma d log 3 n) ( d
d) );
completing the proof. 2
3 Bounding the eigenvalues
In this section, we prove Proposition 2.1. Let 3 be as in Section
2. We start with the following lemma.
Lemma 3.1 There exists a constant fi ? 0 such that, almost surely, for any subset X of 2 \Gammafi d n
vertices,
Proof As in the proof of Lemma 2.6, the probability that there exists a subset X of cardinality
ffln such that e(X; is at most
3n
ffln
if log(1=ffl) ! d=b, where b is a sufficiently large constant. Therefore, if fi is a sufficiently small
constant, this probability goes to 0 as n goes to infinity. 2
Proof of Proposition 2.1
Parts (i) and (ii) are simple. By the variational definition of eigenvalues (see [19, p. 99]), - 1
is simply the maximum of x t Ax=(x t x) where the maximum is taken over all nonzero vectors x.
Therefore, by taking x to be the all 1 vector we obtain the well known result that - 1 is at least
the average degree of G 0 . By the known estimates for Binomial distributions, the average degree
of G is (1 + o(1))2d. on the other hand, Lemma 3.1 can be used to show that
as it easily implies that the number of vertices of degree greater than 5d in each color class of G
is almost surely less than 2 \Gammafi d n. Hence, the average degree of G 0 is at least (1 \Gamma 2 \Gamma\Omega\Gamma d) )2d. This
proves (i).
The proof of (ii) is similar. It is known [19, p. 101] that
where the minimum is taken over all two dimensional subspaces F of R 3n . Let F denote the 2-
dimensional subspace of all vectors
denotes the number of edges of G 0 between W i and W j . Almost surely e 0
d) )nd for all 1
follows that x t Ax=(x t x) - \Gamma(1 \Gamma 2 \Gamma\Omega\Gamma d) )d almost surely for all x 2 F , implying that - 3n -
d) )d, and establishing (ii).
The proof of (iii) is more complicated. Its assertion for somewhat bigger p (for example, for
can be deduced from the arguments of [10]. To prove it for the graph G 0 and p - c=n
we use the basic approach of Kahn and Szemer'edi in [11], where the authors show that the second
largest eigenvalue in absolute value of a random d-regular graph is almost surely O(
d). (See also
[9] for a different proof.) Since in our case the graph is not regular a few modifications are needed.
Our starting point is again the variational definition of the eigenvalues, from which we will deduce
that it suffices to show that almost surely the following holds.
Lemma 3.2 Let S be the set of all unit vectors
d) for all x 2 S.
The matrix A consists of nine blocks arising from the partition of its rows and columns according
to the classes W j . It is clearly sufficient to show that the contribution of each block to the sum
x t Ax is bounded, in absolute value, by O(
d). This, together with a simple argument based on
ffl-nets (see [11], Proposition 2.1) can be used to show that Lemma 3.2 follows from the following
statement.
denote the set of all vectors x of length n every coordinate of
which is an integral multiple of ffl=
n, where the sum of coordinates is zero and the l 2 -norm is at
most 1. Let B be a random n by n matrix with 0; 1 entries, where each entry of B, randomly and
independently, is 1 with probability d=n.
Lemma 3.3 If d exceeds a sufficiently large absolute constant then almost surely, jx t Byj - O(
d)
for every x; y 2 T for which x if the corresponding row of B has more than 5d nonzero entries
and y if the corresponding column of B has more than 5d nonzero entries.
The last lemma is proved, as in [11], by separately bounding the contribution of terms x u y v with
small absolute values and the contribution of similar terms with large absolute values. Here is a
description of the details that differ from those that appear in [11]. Let C denote the set of all
pairs (u; v) with jx u y
d=n and let
. As in [11] one can show that
the absolute value of the expectation of X is at most
d. Next one has to show that with high
probability X does not deviate from its expectation by more than c
d. This is different (and
in fact, somewhat easier) than the corresponding result in [11], since here we are dealing with
independent random choices. It is convenient to use the following variant of the Chernoff bound.
Lemma 3.4 Let a am be (not necessarily positive) reals, and let Z be the random variable
randomly and independently, to be 1 with probability p
and 0 with probability
ce c pD for some positive
constants c; S. Then Pr
For the proof, one first proves the following.
Lemma 3.5 Let c be a positive real. Then for every x - c,
Proof. Define
Therefore, f 00 (x) - 0 for all x - c and as f 0 shows that f 0
implying that f(x) is nonincreasing for x - 0 and nondecreasing for
Proof of Lemma 3.4.
e c pD , then, by assumption, -a i - c for all i. Therefore, by the
above lemma,
E(e -Z
Y
[pe
Y
Y
e c
e c
a 2
Therefore,
Applying the same argument to the random variable defined with respect to the reals \Gammaa i , the
assertion of the lemma follows. 2
Using Lemma 3.4 it is not difficult to deduce that almost surely the contribution of the pairs in
C to jx t Byj is O(
d). This is because we can simply apply the lemma with with the a i 's
being all the terms x u y v where (u; ce c
d for some c ? 0.
Since here jSa ce c p
d
ce c pD, we conclude that for every fixed vectors x and y in T , the
probability that X deviates from its expectation (which is O(
d)) by more than ce c
d is smaller
than 2e \Gammac 2 e c n=2 , and since the cardinality of T is only b n for some absolute constant
can choose c so that X would almost surely not deviate from its expectation by more than ce c p
d.
The contribution of the terms x u y v whose absolute values exceed
d=n can be bounded by
following the arguments of [11], with a minor modification arising from the fact that the maximum
number of ones in a row (or column) of B can exceed d (but can never exceed 5d in a row or a
column in which the corresponding coordinates x u or y v are nonzero). We sketch the argument
below. We start with the following lemma.
Lemma 3.6 There exists a constant C such that, with high probability, for any distinct color classes
any subset U of V 1 and any subset W of V 2 such that jU j - jW j, at least one of the
following two conditions hold:
2. e 0
is the number of edges in G 0 between U and W , and -(U; W jd=n is the
expected number of edges in G between U and W .
Proof. Condition 1 is clearly satisfied if jW j - n=2, since the maximum degree in G 0 is at most
5d. So we can assume without loss of generality that Give two subsets U and
W satisfying the requirements of the lemma, define to be the unique positive real
number such that fi-(U; W ) log will be determined later.)
Condition 2 is equivalent to e 0 (U; W ) - fi-(U; W ). Thus U; W violate Condition 1 as well as
Condition 2 only if e 0 Hence, by standard Chernoff
bounds, the probability of this event is at most e \Gammafl
absolute
constant Denoting jW j=n by b, the probability that there exist two subsets U and W that
do not satisfy either condition is at mostX
b: bn integer -n=2
bn
b: bn integer -n=2
if C is a sufficiently large constant. 2
Kahn and Szemer'edi [11] show that for any d-regular graph satisfying the conditions of Lemma 3.6
(without restriction on the ranges of U and W ), the contribution of the terms x u y v whose absolute
values exceed
d=n is O(
d). Up to replacing some occurences of d by 5d, the same proof shows
that, for any 3-colorable graph of maximum degree 5d satisfying the conditions of Lemma 3.6, the
contribution of the terms x u y v whose absolute values exceed
d=n is O(
d). This implies the
assertion of Lemma 3.3, which implies Lemma 3.2.
To deduce (iii), we need the following lemma.
Lemma 3.7 Let F denote, as before, the 2-dimensional subspace of all vectors
satisfying x almost surely, for all f 2 F we
have
Proof. Let x; y be as in the proof of Lemma 2.3. Note that x t and that both jjxjj 2 and jjyjj 2
are \Theta(n). Thus every vector f 2 F can be expressed as the sum of two orthogonal vectors x 0 and
proportional to x and y respectively. Lemma 2.3 shows that
implies that Similarly, it can be shown
that We conclude the proof of the lemma using the triangle inequality
We now show that - 2 - O(
d) by using the formula -
H ranges over the linear subspaces of R 3n of codimension 1. Indeed, let H be the set of vectors
whose sum of coordinates is 0. Any x 2 H is of the form f and s is a multiple of
a vector in S, and so
As
As
Number of vertices d
1000 12
100000 8

Figure

1: Implementation results.
O(
djjsjjjjf
O(
O(
This implies the desired upper bound on - 2 .
The bound j- 3n\Gamma2 j - O(
d) can be deduced from similar arguments, namely by showing that
d), for any x 2 F ? . This completes the proof of Proposition 2.1. 2
4 Implementation and Experimental Results.
We have implemented the following tuned version of our algorithm. The first two phases are as
described in Section 1. In the third phase, we find the minimum i such that, after repeatedly un-
coloring every vertex colored j that has less than i neighbors colored l, for some l 2 f1; 2; 3g \Gamma fjg,
the algorithm can find a proper coloring using brute force exhaustive search on every component
of uncolored vertices. If the brute force search takes more steps than the first phase (up to a multiplicative
constant), the algorithm fails. Otherwise, it outputs a legal coloring. The eigenvectors
e 3n and e 3n\Gamma1 are calculated approximately using an iterative procedure. The coordinates of the
initial vectors are independent random variables uniformly chosen in [0; 1].
The range of values of p where the algorithm succeeded was in fact considerably larger than
what our analysis predicts. Figure 1 shows some values of the parameters for which we tested our
algorithm. For each of these parameters, the algorithm was run on more than a hundred graphs
drawn from the corresponding distribution, and found successfully a proper coloring for all these
tests. The running time was a few minutes on a Sun SPARCstation 2 for the largest graphs. The
algorithm failed for some graphs drawn from distributions with smaller integral values of d than
the one in the corresponding row. Note that the number of vertices is not a multiple of 3; the size
of one color class exceeds the others by one.
Concluding remarks
1. There are many heuristic graph algorithms based on spectral techniques, but very few rigorous
proofs of correctness for any of those in a reasonable model of random graphs. Our main
result here provides such an example. Another example is the algorithm of Boppana [7],
who designed an algorithm for graph bisection based on eigenvalues, and showed that it finds
the best bisection almost surely in an appropriately defined model of random graphs with a
relatively small bisection width. Aspvall and Gilbert [1] gave a heuristic for graph coloring
based on eigenvectors of the adjacency matrix, and showed that their heuristic optimally colors
complete 3-partite graphs as well as certain other classes of graphs with regular structure.
2. By modifying some of the arguments of Section 2 we can show that if p is somewhat bigger
(p - log 3 n=n suffices) then almost surely the initial coloring V 0
i that is computed from
the eigenvectors e 3n\Gamma1 and e 3n in the first phase of our algorithm is completely correct. In
this case the last two phases of the algorithm are not needed. By refining the argument in
Subsection 2.2, it can also be shown that if log n=n the third phase of the algorithm is
not needed, and the coloring obtained by the end of the second phase will almost surely be
the correct one.
3. We can show that a variant of our algorithm finds, almost surely, a proper coloring in the
model of random regular 3-colorable graphs in which one chooses randomly d perfect matchings
between each pair of distinct color classes, when d is a sufficiently large absolute constant.
Here, in fact, the proof is simpler, as the smallest two eigenvalues (and their corresponding
are known precisely, as noted in Subsection 1.2.
4. The results easily extend to the model in which each vertex first picks a color randomly,
independently and uniformly, among the three possibilities, and next every pair of vertices of
distinct colors becomes an edge with probability p (? c=n).
5. If positive constant c, it is not difficult to show
that almost surely G does not have any subgraph with minimum degree at least 3, and hence
it is easy to 3-color it by a greedy-type (linear time) algorithm. For values of p which are
bigger than this c=n but satisfy n=n), the graph G is almost surely disconnected,
and has a unique component of \Omega\Gamma n) vertices, which is called the giant component in the
study of random graphs (see, e.g., [2], [4]). All other components are almost surely sparse,
i.e., contain no subgraph with minimum degree at least 3, and can thus be easily colored in
total linear time. Our approach here suffices to find, almost surely, a proper 3-coloring of the
giant component (and hence of the whole graph) for all p - c=n, where c is a sufficiently large
absolute constant, and there are possible modifications of it that may even work for all values
of p. At the moment, however, we are unable to obtain an algorithm that provably works
for all values of p almost surely. Note that, for any constant c, if p ! c=n then the greedy
algorithm will almost surely color G 3n;p;3 with a constant number of colors. Thus, our result
implies that G 3n;p;3 can be almost surely colored in polynomial time with a constant number
of colors for all values of p.
6. Our basic approach easily extends to k-colorable graphs, for every fixed k, as follows. Phase
2 and Phase 3 of the algorithm are essentially the same as in the case needs
to be modified to extract an approximation of the coloring. Let e i , i - 1, be an eigenvector of
corresponding to its ith largest eigenvalue (replace 5d by 5kd in the definition of G 0 .) Find
vectors
kn in
and z, let W ffl be the set of
vertices whose coordinates in x i are in (z \Gamma ffl; z ffl). If, for some i and z, both jW ffl k j and
deviate from n by at most fi k n=d, where ffl k and fi k are constants depending on k, color
the elements in W ffl k
with a new color and delete them from the graph. Repeat this process
until the number of vertices left is O(n=d), and color the remaining vertices in an arbitrary
manner.
7. The existence of an approximation algorithm based on the spectral method for coloring arbitrary
graphs is a question that deserves further investigation (which we do not address here.)
Recently, improved approximation algorithms for graph coloring have been obtained using
semidefinite programming [14], [5].

Acknowledgement

We thank two anonymous referees for several suggestions that improved the
presentation of the paper.



--R

Graph coloring using eigenvalue decomposition
The Probabilistic Method
Some tools for approximate 3-coloring


Journal of Algorithms 19
Eigenvalues and graph bisection: An average case analysis
The solution of some random NP-Hard problems in polynomial expected time
on the second eigenvalue and random walks in random d-regular graphs

on the second eigenvalue in random regular graphs
Computers and intractability: a guide to the theory of NP-completeness
Reducibility among combinatorial problems
Approximate graph coloring by semidefinite program- ming
Expected behavior of graph colouring algorithms
A randomised 3-colouring algorithm
A First Course in Numerical Analysis
Almost all k-colorable graphs are easy to color
The Algebraic Eigenvalue Problem
--TR

--CTR
David Eppstein, Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.329-337, January 07-09, 2001, Washington, D.C., United States
Amin Coja-Oghlan, A spectral heuristic for bisecting random graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Amin Coja-oghlan, The Lovsz Number of Random Graphs, Combinatorics, Probability and Computing, v.14 n.4, p.439-465, July 2005
Michael Krivelevich , Dan Vilenchik, Solving random satisfiable 3CNF formulas in expected polynomial time, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.454-463, January 22-26, 2006, Miami, Florida
Richard Beigel , David Eppstein, 3-coloring in time O(1.3289n), Journal of Algorithms, v.54 n.2, p.168-204, February 2005
Abraham D. Flaxman , Alan M. Frieze, The diameter of randomly perturbed digraphs and some applications, Random Structures & Algorithms, v.30 n.4, p.484-504, July 2007
Amin Coja-oghlan , Andreas Goerdt , Andr Lanka, Strong Refutation Heuristics for Random k-SAT, Combinatorics, Probability and Computing, v.16 n.1, p.5-28, January 2007
Amin Coja-Oghlan , Andreas Goerdt , Andr Lanka , Frank Schdlich, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT, Theoretical Computer Science, v.329 n.1-3, p.1-45, 13 December 2004
Paul Beame , Joseph Culberson , David Mitchell , Cristopher Moore, The resolution complexity of random graphk-colorability, Discrete Applied Mathematics, v.153 n.1, p.25-47, 1 December 2005
graph eigenvalues;graph coloring;algorithms;random graphs