6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Andrew D. King
    Commented Feb 20, 2013 at 23:45
  • $\begingroup$ It certainly cannot be edge-transitive, since the parameters can be shown to be equal in that case. $\endgroup$
    – David Roberson
    Commented Feb 21, 2013 at 1:59
  • $\begingroup$ @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. $\endgroup$
    – David Roberson
    Commented Feb 22, 2013 at 18:58

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For the graph in question, computing $\theta$ and $\theta'$ reduces to linear programming, as it comes from a commutative association scheme. $\endgroup$
    – Dima Pasechnik
    Commented Mar 25, 2013 at 12:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .