For $\alpha \ge 2$, an $\alpha$-vector coloring of a graph $X$ is an assignment of unit vectors to the vertices of $X$ such that vectors assigned to adjacent vertices have inner product less than or equal to $\frac{1}{1-\alpha}$. A strict $\alpha$-vector coloring requires equality for the inner product.
The vector chromatic number of a graph $X$, denoted $\chi_{vec}(X)$, is defined to be the minimum $\alpha$ for which $X$ has an $\alpha$-vector coloring. Strict vector chromatic number is defined analogously. It is known that the strict vector chromatic number of $X$ is equal to the Lovasz theta function of the complement of $X$.
Are there any finite graphs known for which the vector and strict vector chromatic numbers are different?
For reference, vector and strict vector colorings and the relation to Lovasz theta come from "Approximate Graph Coloring by Semidefinite Programming" by Karger, Motwani, and Sudan.
Best Answer
Apparently, Schrijver defined a function $\vartheta'$ in the paper A Comparison of the Delsart and Lovasz Bounds which (I am pretty sure) is equivalent to vector chromatic number of the complement. Furthermore, he gives an example of a vertex transitive graph $X$ which has $\vartheta'(X) < \vartheta(X)$. The graph $X$ has the $01$-strings of length 6 as its vertices, and two such strings are adjacent if they are at Hamming distance at most 3. Taking complements obviously provides an example answering my question in the affirmative.
Considering the graph $Y = \overline{X}$, two strings are adjacent if they are at Hamming distance 4 or more. We can then replace 01-strings with $\pm 1$ vectors in the obvious way, and then normalize these vectors. Now, adjacency will correspond to two vectors having inner product less than or equal to $-1/3$. This then implies that $\chi_{vec}(Y) \le 4$, which happens to be the clique number of $Y$, and thus $\chi_{vec}(Y) = 4$ (this value is given in Schrijver's paper, but it is not discussed how he comes to this value). According to Schrijver, $\bar{\vartheta}(Y) = 16/3 > 4$. Obviously, the way $Y$ was defined gave rise to a "natural" vector coloring, and I would guess that other similarly defined graphs might be examples of graphs with vector chromatic number less than strict vector chromatic number.
Interestingly, Schrijver's paper was written in 1979, about 15 years before Karger, Motwani, and Sudan defined vector chromatic number.