Next: Graphs with largest eigenvalue Up: The spectrum of a Previous: Diameter

# 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 is the size of the largest clique in . The independence number is the size of the largest coclique in . The chromatic number is the minimum number of colours of a proper vertex colouring of .

Proposition 1.10.1   (Hoffman-Haemers) Let be a graph on vertices with largest eigenvalue , second largest eigenvalue , and smallest eigenvalue . Then

(i) is at most the number of nonnegative (nonpositive) eigenvalues of .

(ii) .

(iii) If is regular, then .

(iv) If is strongly regular, then .

Proof:     (i) This follows by interlacing.

(ii) Suppose has a proper colouring with colours. Let be the diagonal matrices with ones on the diagonal for the positions of the -th colour class and zeroes elsewhere. Then . Let be an eigenvector for the eigenvalue of , and put . Then so that .

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

with eigenvalues and . By interlacing (Corollary 1.5.3) we find . Since this is equivalent to the stated inequality.

(iv) We have . When is strongly regular we have and and (with standard notation , ) (because both sides coincide on the eigenvectors for and , so the left hand side is a multiple of , but it is on the diagonal), so that , and the claim follows from part (iii).

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

Example     The strongly regular Higman-Sims graph has parameters and eigenvalues of multiplicities , respectively. Each point neighbourhood is a coclique of size 22, and we have equality in (i).

Next: Graphs with largest eigenvalue Up: The spectrum of a Previous: Diameter
Andries Brouwer 2003-09-30