I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.
($G$ has vector chromatic number $q$ if there is an assignment $x\colon V \rightarrow \mathbf R^d$, where intuitively the vectors associated with neighbouring vertices are far apart. The requirement is $\langle x(v), x(w)\rangle \leq -1/(q-1)$. For example, for $q=3$, the vertices of a triangle suffice.)
A graph’s vector chromatic number is no larger than the chromatic number: $\chi_v(G)\leq \chi(G)$. Examples are known of graphs with $\chi_v(G)=3$ $\chi(G)=n^\delta$. (The original paper by Karger, Motwani, Sudan [JACM, 45:246-265] (manuscript) suggests generalised Kneser graphs, a more recent paper uses a construction based on random unit vectors.)
I think I have an example graph $K$ with $\chi_v(K)=4$ and $\chi(K)=8$ (based on computer calculation). This graph has 20 vertices and 90 edges.
Is there a smaller example? A tempting avenue would be to provide a concrete vector 3-colouring of the Chvatal or Grötzsch graph, if such a beast exists.
($\chi_v$ need not be an integer, but it would be nice. Update: As pointed out below, the nonintegral case is indeed easy. Thanks.)
Update: Grötzsch and Chvátal
I couldn’t resist thinking about vector 3-colouring the Chvátal and Grötzsch graphs.
The Grötsch graph can be vector 3-coloured as follows: Put the degree five node on the North pole. The 5 degree-4 nodes are evenly placed on the same latitude, around 77 degrees from North: imagine a pentragram painted on Earth’s northern hemisphere. The remaining 5 nodes (of degree 3) end up on the Southern hemisphere, around 135 degree from North. The have the same longitude as the 5 others. (I’ll upload a drawing when I have one, but it’s harder to draw geodesic lines in TikZ than I thought.)
According to an SDP solver, Chvátal also admits a vector 3-colouring, but the output is just a bunch of vectors in 5 dimensions that I have difficulties interpreting.
(A third attempt failed: Inspired by Yury’s construction, take the 5-cycle and add an apex vertex adjacent to all the others. This graph has chromatic number 4. But according to my solver it is not vector 3-colourable.)