Take the 2-minute tour ×

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $\chi \(\overline{G})$. When $G$ is perfect then $$\alpha(G)=\vartheta(G)=\chi \(\overline{G}).$$ Give examples of graphs $G$ such that $$\alpha(G)<\vartheta(G)=\chi \(\overline{G}).$$

share|improve this question

1 Answer 1

up vote 11 down vote accepted

Suppose $G$ is a $k$-regular graph on $n$ vertices, with least eigenvalue $\tau$. Lovasz proved that $$ \theta(G) \le \frac{n}{1-\frac{k}{\tau}}. $$ Further if the automorphism group of $G$ acts arc-transitively, then equality holds. In fact equality holds if G is a single class in a homogeneous coherent configuration, for example, if $G$ is a strongly regular graph.

Class 1: Latin square graphs. Take the graph whose vertices are the $n^2$ cells of and $n\times n$ Latin square, where two cells are adjacent if they are in the same row, same column, or have the same contents. This graph is regular with valency $3(n-1)$ and least eigenvalue $-3$ and so $\theta(G)=n$. But if the Latin square is the multiplication table of a cyclic group of even order then $\alpha(G) < n$ (because cyclic Latin squares do not have transversals, but you can find a short proof on page 225 of one of my favorite books on algebraic graph theory). The vertices in a given column form a clique of size $n$ and so we see that $\chi(\bar{G})=n$ for any Latin square of order $n$.

Class 2: generalized quadrangles: A GQ with parameters $(s,t)$ is a collection of points and lines satisfying some axioms, in particular each line contains exactly $s+1$ points. Deem two points adjacent if they are collinear. If $s,t>1$ this gives a strongly regular graph on $(s+1)(st+1)$ vertices with valency $s(t+1)$ and least eigenvalue $-t-1$. Hence $\theta(G) = st+1$ and a coclique of size $st+1$ is known as an ovoid. The points on line forms a clique of size $s+1$, and a set of lines that partition the point set is called a spread. Hence you want GQ's with spreads but no ovoids. For actual examples, I refer you to Payne and Thas's book on GQ's---the GQ's $Q(5,q)$ work.

share|improve this answer
Thank you for the useful and beautiful answer. –  Simone Severini Nov 19 '10 at 0:52

Your Answer


