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

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.

share|improve this question
    
I don't have an answer, but such a graph would definitely be imperfect and I would be extremely surprised if it were vertex-transitive. –  Andrew D. King Feb 20 '13 at 23:45
    
It certainly cannot be edge-transitive, since the parameters can be shown to be equal in that case. –  David Roberson Feb 21 '13 at 1:59
    
@Andrew D. King: Out of curiosity, why would you be surprised if it were a vertex transitive graph? Is it because you think that $\chi_{vec}(X \cup Y) \le \chi_{vec}(X)\chi_{vec}(Y)$ should be true as it is for many other chromatic numbers? Here $X \cup Y$ means edge union of graphs on the same vertex set. I ask because I think it should be true and it would imply that vector and strict vector chromatic number are equal for vertex transitive graphs. –  David Roberson Feb 22 '13 at 18:58
add comment

1 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.

share|improve this answer
    
For the graph in question, computing $\theta$ and $\theta'$ reduces to linear programming, as it comes from a commutative association scheme. –  Dima Pasechnik Mar 25 '13 at 12:07
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.