<p>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} &lt; 3 = \chi(C_5) . \qquad\text{[Lovász]}$$</p>

<p>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) &amp;= \max(\chi(G_1), \chi(G_2)) = \chi(G_1) = 6.\\
\chi_v(G) &amp;= \max(\chi_v(G_1), \chi_v(G_2)) = \max(2\cdot \sqrt{5}, 5) = 5.
\end{align*}</p>

CC BY-SA 3.0
2013-04-13T21:10:39.467Z
2013-04-13T21:10:39.467Z
Yury
<p>Here it an embedding of the Grötzsch graph on the unit sphere: <img src="https://i.sstatic.net/z63hR.png" alt="enter image description here">
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).</p>

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

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

<p>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:<img src="https://i.sstatic.net/POMCS.png" alt="enter image description here"></p>

<p>Finally, a view from above the South pole: <img src="https://i.sstatic.net/d3X2P.png" alt="enter image description here"></p>

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

CC BY-SA 3.0
2013-04-17T06:49:02.063Z
2013-04-17T06:49:02.063Z
Thore Husfeldt
<p>I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)&lt;\chi(G)$.</p>

<p>($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.)</p>

<p>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] (<a href="http://people.csail.mit.edu/karger/Papers/color.ps" rel="nofollow">manuscript</a>) suggests generalised Kneser graphs, a more recent paper uses a construction based on random unit vectors.)</p>

<p>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.</p>

<p>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.</p>

<p>($\chi_v$ need not be an integer, but it would be nice. Update: As pointed out below, the nonintegral case is indeed easy. Thanks.)</p>

<h3>Update: Grötzsch and Chvátal</h3>

<p>I couldn’t resist thinking about vector 3-colouring the Chvátal and Grötzsch graphs. </p>

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

<p>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.</p>

<p>(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.)</p>

CC BY-SA 3.0
2013-04-13T05:22:36.883Z
Could you provide a link or a defn for vector chromatic number ?
Suresh Venkat
CC BY-SA 3.0
2013-04-13T05:47:02.067Z
$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5)$, where $C_5$ is a cycle on 5 vertices. $C_5$ is the smallest graph $G$ s.t. $\chi_v(G) \neq \chi(G)$.
Yury
<ds.algorithms><graph-theory><co.combinatorics><graph-algorithms><graph-colouring>
Small graph with gap between chromatic and vector chromatic number?
Thore Husfeldt
# Small graph with gap between chromatic and vector chromatic number?

(Asked by: username_0 on 2013-04-12)

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](http://people.csail.mit.edu/karger/Papers/color.ps)) 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 username_2’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.)

**Tags:** ds.algorithms, graph-theory, co.combinatorics, graph-algorithms, graph-colouring

> **Comments:**
> **username_1**: Could you provide a link or a defn for vector chromatic number ?  
> **username_2**: $\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5)$, where $C_5$ is a cycle on 5 vertices. $C_5$ is the smallest graph $G$ s.t. $\chi_v(G) \neq \chi(G)$.  

---

## 2 answers

### Answer by username_2 on 2013-04-13. Score: 7 | Accepted answer

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 by username_0 on 2013-04-17. Score: 3

Here it an embedding of the Grötzsch graph on the unit sphere: ![enter image description here](https://i.sstatic.net/z63hR.png)
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:![enter image description here](https://i.sstatic.net/POMCS.png)

Finally, a view from above the South pole: ![enter image description here](https://i.sstatic.net/d3X2P.png)

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


---

