From Independent Sets to Colorings
A proper coloring partitions the vertices into independent sets: no two vertices of the same color are adjacent. Consequently, an upper bound on the size of any independent set limits how many vertices each color class can contain. For a regular graph, the least eigenvalue of the adjacency matrix gives precisely such a bound. Applying it to every color class yields Hoffman's lower bound for the chromatic number.
All graphs in this tutorial are finite and simple. The adjacency matrix \(\mathbf A(G)\) has entry \(1\) in positions \(u,v\) when \(uv\in E(G)\), and entry \(0\) otherwise. It is a real symmetric matrix, so its eigenvalues are real. Write \(r\) for the degree of every vertex in an \(r\)-regular graph, and write \(s\) for the least eigenvalue of \(\mathbf A(G)\).
We consider a nonempty \(r\)-regular graph with \(r\ge 1\). The all-ones vector is an eigenvector of \(\mathbf A(G)\) with eigenvalue \(r\), since every vertex has \(r\) neighbors. Also, \(s<0\): the sum of the eigenvalues is the trace of \(\mathbf A(G)\), which is \(0\), while at least one eigenvalue is the positive number \(r\). If all eigenvalues were nonnegative, their sum could not be \(0\). Thus the denominator \(-s\) in the bound below is positive. The case \(r=0\) is excluded: a nonempty edgeless graph has chromatic number \(1\), but its least eigenvalue is \(0\), so this formula does not apply.
The Independent-Set Bound
We first obtain the spectral bound on an independent set. This is the key input: a coloring cannot use fewer color classes than are needed to cover all vertices with sets of at most this size.
Proof. Let \(a=|S|\). If \(a=0\), the claimed inequality holds because \(-ns/(r-s)>0\). Suppose \(a>0\), and let \(x\) be the vector whose coordinate is \(1\) at vertices in \(S\) and \(0\) elsewhere. Since \(S\) is independent, no edge has both endpoints in \(S\), so \(x^{T}\mathbf A(G)x=0\). Write \(\mathbf 1\) for the all-ones vector and decompose $$ x=\frac{a}{n}\mathbf 1+y,\qquad \mathbf 1^{T}y=0. $$ Because \(\mathbf A(G)\mathbf 1=r\mathbf 1\) and \(\mathbf A(G)\) is symmetric, the subspace orthogonal to \(\mathbf 1\) is invariant under \(\mathbf A(G)\). Every eigenvalue on that subspace is at least \(s\), so expanding \(y\) in an orthonormal eigenbasis gives \(y^{T}\mathbf A(G)y\ge s\,y^{T}y\). The cross terms between \(\mathbf 1\) and \(y\) vanish, and therefore $$ 0=x^{T}\mathbf A(G)x =\frac{r a^{2}}{n}+y^{T}\mathbf A(G)y \ge \frac{r a^{2}}{n}+s\,y^{T}y. $$ The decomposition is orthogonal, so \(y^{T}y=x^{T}x-a^{2}/n=a-a^{2}/n\). Substitution yields $$ 0\ge \frac{r a^{2}}{n}+s\left(a-\frac{a^{2}}{n}\right) =a\left(s+\frac{(r-s)a}{n}\right). $$ Since \(a>0\), divide by \(a\), then rearrange using \(r-s>0\): $$ \frac{(r-s)a}{n}\le -s,\qquad a\le \frac{-ns}{r-s}. $$ This proves the bound. \(\square\)
Hoffman's Chromatic-Number Bound
Proof. Let \(k=\chi(G)\), and let \(C_1,\ldots,C_k\) be the nonempty color classes of a proper coloring using \(k\) colors. Each \(C_i\) is independent, so the independent-set bound gives \(|C_i|\le -ns/(r-s)\) for every \(i\). Summing over the classes, which partition the \(n\) vertices, gives $$ n=\sum_{i=1}^{k}|C_i| \le k\frac{-ns}{r-s}. $$ Divide by \(n>0\), and then by \((-s)/(r-s)>0\). It follows that $$ k\ge \frac{r-s}{-s}=1-\frac{r}{s}. $$ Because \(k\) is an integer, it is at least the ceiling of the right-hand side as well. \(\square\)
The lower bound uses only the degree and the least eigenvalue, so it is available even when finding an optimal coloring directly is difficult. It is a necessary condition, not generally an exact formula for \(\chi(G)\). To use it, check that the graph is regular, identify its least adjacency eigenvalue, and keep its negative sign when substituting into \(1-r/s\).
Worked Example: The Complete Graph \(K_4\)
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Every vertex has degree \(3\), so \(r=3\). Its adjacency matrix is \(J-I\), where \(J\) is the \(4\)-by-\(4\) all-ones matrix and \(I\) is the identity matrix. The all-ones vector has eigenvalue \(4-1=3\). Every vector orthogonal to the all-ones vector is sent to its negative by \(J-I\), so the other three eigenvalues are \(-1\). Thus \(s=-1\).
Substituting the values gives $$ 1-\frac{r}{s}=1-\frac{3}{-1}=1+3=4, $$ and hence \(\chi(G)\ge 4\). Giving every vertex a different color uses \(4\) colors, so \(\chi(G)=4\).
Check: Each color class in \(K_4\) contains at most one vertex, so four classes are necessary. This agrees with the spectral bound.
Worked Example: The Complete Bipartite Graph \(K_{3,3}\)
Let \(X=\{x_1,x_2,x_3\}\), \(Y=\{y_1,y_2,y_3\}\), and let \(G=K_{3,3}\) have vertex set \(X\cup Y\) and edge set \(\{x_i y_j:1\le i\le 3,\ 1\le j\le 3\}\). Every vertex has degree \(3\), so \(r=3\). To find the eigenvalues, consider vectors whose coordinates are constant, with value \(p\) on \(X\) and \(q\) on \(Y\). The adjacency matrix sends such a vector to one with value \(3q\) on \(X\) and \(3p\) on \(Y\). Thus the constant-block vectors with \(p=q\) and \(p=-q\) have eigenvalues \(3\) and \(-3\), respectively.
If a vector has coordinate sum \(0\) on \(X\) and is zero on \(Y\), then each coordinate of its image on \(Y\) is the sum of its coordinates on \(X\), hence is \(0\); its image on \(X\) is also \(0\). The same argument applies to vectors supported on \(Y\) with coordinate sum \(0\). These two subspaces each have dimension \(2\), giving four more eigenvalues equal to \(0\). The six eigenvalues are therefore \(3,-3,0,0,0,0\), and \(s=-3\).
The bound is $$ 1-\frac{r}{s}=1-\frac{3}{-3}=2, $$ so \(\chi(G)\ge 2\). Coloring \(X\) with one color and \(Y\) with another is proper, because every edge joins the two sets. Thus \(\chi(G)=2\).
Check: The eigenvalues account for all six coordinates: one eigenvalue \(3\), one \(-3\), and four \(0\)'s. The coloring uses two colors, matching the lower bound.
Worked Example: The Triangular Prism
Let \(G\) have vertex set \(\{a,b,c,A,B,C\}\) and edge set \(\{ab,bc,ca,AB,BC,CA,aA,bB,cC\}\). The vertices \(a,b,c\) form one triangle, \(A,B,C\) form another, and the remaining three edges join corresponding vertices. Every vertex has degree \(3\), so \(r=3\).
For a vector whose coordinates on the two triangles agree, the adjacency action reduces to the adjacency action of a triangle plus the identity: each vertex receives the sum of the other two coordinates in its triangle and its corresponding coordinate in the other triangle. The triangle adjacency matrix has eigenvalues \(2,-1,-1\), so this subspace gives eigenvalues \(3,0,0\). For a vector whose coordinates on the second triangle are the negatives of those on the first, the action reduces to the triangle adjacency matrix minus the identity, giving eigenvalues \(1,-2,-2\). These two three-dimensional subspaces together account for all six eigenvalues. Hence the least eigenvalue is \(s=-2\).
Substitution gives $$ 1-\frac{r}{s}=1-\frac{3}{-2}=1+\frac{3}{2}=\frac{5}{2}. $$ Since \(\chi(G)\) is an integer, \(\chi(G)\ge \lceil 5/2\rceil=3\). The top triangle requires three different colors. Assign \(a,b,c\) colors \(1,2,3\), respectively, and assign \(A,B,C\) colors \(2,3,1\), respectively. Each bottom-triangle edge joins different colors, and the matching edges \(aA,bB,cC\) join colors \(1\) and \(2\), \(2\) and \(3\), and \(3\) and \(1\), respectively. This is a proper coloring, so \(\chi(G)=3\).
Check: The spectrum \(3,0,0,1,-2,-2\) has six entries, as required for a graph on six vertices. The spectral lower bound is \(5/2\), whose ceiling is \(3\), agreeing with the exhibited coloring.
Interpreting the Bound and Avoiding a Sign Error
The bound becomes stronger when the negative least eigenvalue is closer to \(0\) relative to the degree; the relevant quantity is \(1-r/s\), with \(s<0\). The integer ceiling matters: a bound of \(5/2\) implies at least \(3\) colors, not \(2\). But even after rounding, the result can be weaker than the true chromatic number. It constrains every coloring through the sizes of its independent classes; it does not itself construct a coloring.
Common mistake: dropping the minus sign. For the triangular prism, \(r=3\) and \(s=-2\). An incorrect substitution that treats \(s\) as \(2\) gives \(1-3/2=-1/2\), which cannot be the intended lower bound. The correction is to substitute the least eigenvalue with its sign: $$ 1-\frac{r}{s}=1-\frac{3}{-2}=\frac{5}{2}. $$ A quick check is that \(r>0\) and \(s<0\), so \(r/s<0\) and \(1-r/s>1\).
Another useful check is to compare the conclusion with the graph's structure. For example, a graph containing a triangle needs at least three colors, since the three vertices of the triangle are pairwise adjacent. If a calculation for such a graph produces a lower bound below \(3\), that does not by itself signal an error—the spectral estimate may be weak—but it cannot replace the direct triangle argument.
Check Your Understanding
Use the hypotheses and derivation above to answer these questions.
- Why must the least adjacency eigenvalue of a nonempty \(r\)-regular graph with \(r\ge 1\) be negative?
- In the independent-set proof, why does the indicator vector of an independent set satisfy \(x^{T}\mathbf A(G)x=0\)?
- A \(4\)-regular graph has least adjacency eigenvalue \(-2\). What lower bound does the theorem give for its chromatic number after rounding to an integer?
- Explain why applying an independent-set bound to each color class gives a lower bound on the number of colors rather than an upper bound.
- Why does the formula for this theorem not apply to a nonempty \(0\)-regular graph?