Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.