12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Could you provide a link or a defn for vector chromatic number ? $\endgroup$ – Suresh Venkat Apr 13 '13 at 5:22
  • 4
    $\begingroup$ $\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)$. $\endgroup$ – Yury Apr 13 '13 at 5:47
7
$\begingroup$

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*}

$\endgroup$
3
$\begingroup$

Here it an embedding of the Grötzsch graph on the unit sphere: 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).

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

Finally, a view from above the South pole: enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.