Cliques, cocliques, chromatic number

A clique in a graph is a set of pairwise adjacent vertices. A coclique in a graph is a set of pairwise nonadjacent vertices. A proper vertex colouring of a graph is an assignment of colours to the verices so that adjacent vertices get different colours. The clique number $\omega(\Gamma)$ is the size of the largest clique in $\Gamma$. The independence number $\alpha(\Gamma)$ is the size of the largest coclique in $\Gamma$. The chromatic number $\chi(\Gamma)$ is the minimum number of colours of a proper vertex colouring of $\Gamma$.

Proposition 1.10.1   (Hoffman-Haemers) Let $\Gamma$ be a graph on $n$ vertices with largest eigenvalue $\theta_1$, second largest eigenvalue $\theta_2$, and smallest eigenvalue $\theta_n$. Then

(i) $\alpha(\Gamma)$ is at most the number of nonnegative (nonpositive) eigenvalues of $A$.

(ii) $\chi(\Gamma) \ge 1 - \theta_1/\theta_n$.

(iii) If $\Gamma$ is regular, then $\alpha(\Gamma) \le n / (1 - \theta_1/\theta_n)$.

(iv) If $\Gamma$ is strongly regular, then $\omega(\Gamma) \le 1 - \theta_1/\theta_n$.

Proof:     (i) This follows by interlacing.

(ii) Suppose $\Gamma$ has a proper colouring with $c$ colours. Let $I_j$ $(1 \le j \le c)$ be the diagonal matrices with ones on the diagonal for the positions of the $j$-th colour class and zeroes elsewhere. Then $\sum_j I_j = I$. Let $u$ be an eigenvector for the eigenvalue $\theta_1$ of $A$, and put $u_j = I_j u$. Then $2(c-1)\theta_n \vert\vert u\vert\vert^2 = 2(c-1)\theta_n \sum_j \vert\vert u_j\... ...sum_{i,j} u_i^\top A u_j = -2 u^\top A u = -2 \theta_1 \vert\vert u\vert\vert^2$ so that $c-1 \ge -\theta_1/\theta_n$.

(iii) Suppose $\Gamma$ is regular of degree $k$ and has a coclique of size $c$. The corresponding partition of the vertex set in two parts gives a matrix of average row sums

$$B = \left(\begin{array}{cc} 0 & k \\ ck/(n-c) & k - ck/(n-c) \\ \end{array}\right)$$

with eigenvalues $k$ and $- ck/(n-c)$. By interlacing (Corollary 1.5.3) we find $- ck/(n-c) \ge \theta_n$. Since $k = \theta_1$ this is equivalent to the stated inequality.

(iv) We have $\omega(\Gamma) = \alpha(\bar{\Gamma})$. When $\Gamma$ is strongly regular we have $\theta_1(\bar{\Gamma}) = n-1-\theta_1$ and $\theta_n(\bar{\Gamma}) = -1-\theta_2$ and (with standard notation $\theta_2 = r$, $\theta_n = s$) $(I-{A \over s})(I - {J-I-A \over -r-1}) = J$ (because both sides coincide on the eigenvectors for $r$ and $s$, so the left hand side is a multiple of $J$, but it is $I$ on the diagonal), so that $n/(1-k/s) = 1 - (n-1-k)/(-r-1)$, and the claim follows from part (iii). $\Box$

Remark     The proof of (ii) only uses that $A$ vanishes where $\Gamma$ has a nonedge; $A$ may have arbitrary values on edges.

Example     The strongly regular Higman-Sims graph has parameters $(v,k,\lambda,\mu) = (100,22,0,6)$ and eigenvalues $22, 2, -8$ of multiplicities $1, 77, 22$, respectively. Each point neighbourhood is a coclique of size 22, and we have equality in (i).