Small graph with gap between chromatic and vector chromatic number?

Question

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

Answer 1

I make my comment an answer. If we don't require that $\chi_v(G)$ is an integer then the smallest example is $G=C_5$ (a cycle on 5 vertices): $$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$

It's not hard to transform this example to an example where $\chi_v(G)$ is integer. Let $G_1$ be a union of two 5-cycles $C_5^{(1)}$ and $C_5^{(2)}$ in which every vertex from $C_5^{(1)}$ is connected to every vertex in $C_5^{(2)}$. Let $G_2=K_5$. Finally, let $G$ be the union of $G_1$ and $G_2$. Then \begin{align*} \chi(G) &= \max(\chi(G_1), \chi(G_2)) = \chi(G_1) = 6.\\ \chi_v(G) &= \max(\chi_v(G_1), \chi_v(G_2)) = \max(2\cdot \sqrt{5}, 5) = 5. \end{align*}

Answer 2

Here it an embedding of the Grötzsch graph on the unit sphere: This corresponds to a vector colouring in the obvious way; e.g., the vertex at the North pole is coloured with the vector (0,0,1).

The Grötsch graph has 3 types of nodes. A single degree 5 nodes (at North). Five degree 4 nodes (on the Northern hemisphere, equidistant to N, you can make out 3 of them). Five degree 3 nodes (on the Southern hemisphere, equidistant to N, you can make out 3 of them).

N is connected to its 5 neighbours on the Southern hemisphere with green edges. (Note that the green edge looks as if it is incident on the degree 4-vertices on the Northern hemisphere, but that’s an artefact of the embedding.)

Viewed from the top, you can make out the pentagram described by the degree 4 nodes, similar to Lovasz’ embedding of $C_5$ in the plane:

Finally, a view from above the South pole:

If my calculations are to be believed, all neighbouring vertices are at more than 120 degrees from each other, so this constitutes a valid vector 3-colouring. The Grötzsch graph is 4-chromatic. 11 vertices, 20 edges. I’m particularly happy about this example because the vector colouring is in 3 dimensions, to you can visualise it. (And draw random hyperplanes in order to explain the KMS graph colouring algorithm.)