Petit graphique avec écart entre le nombre chromatique et le nombre chromatique vectoriel?

Je cherche un petit graphe $G$ dont le nombre chromatique vectoriel est plus petit que le nombre chromatique, $\chi_v(G)<\chi(G)$ .

( $G$ a vecteur chromatique $q$ s'il y a une affectation $x\colon V \rightarrow \mathbf R^d$ , où intuitivement les vecteurs associés à l'exigence de sommets voisins sont éloignés. $\langle x(v), x(w)\rangle \leq -1/(q-1)$ . Par exemple, pour $q=3$ , les sommets d'un triangle suffisent.)

Le nombre chromatique vectoriel d'un graphique n'est pas supérieur au nombre chromatique: $\chi_v(G)\leq \chi(G)$ . On connaît des exemples de graphes avec $\chi_v(G)=3$ $\chi(G)=n^\delta$ . (L'article original de Karger, Motwani, Soudan [JACM, 45: 246-265] ( manuscrit ) suggère des graphiques de Kneser généralisés, un article plus récent utilise une construction basée sur des vecteurs unitaires aléatoires.)

Je pense avoir un exemple de graphique $K$ avec $\chi_v(K)=4$ et $\chi(K)=8$ (basé sur un calcul informatique). Ce graphique a 20 sommets et 90 arêtes.

Y a-t-il un exemple plus petit? Une avenue tentante serait de fournir un vecteur concret 3-coloration du graphique de Chvatal ou de Grötzsch, si une telle bête existe.

( $\chi_v$ n'a pas besoin d'être un entier, mais ce serait bien. Mise à jour: Comme indiqué ci-dessous, le cas non intégré est en effet facile. Merci.)

Mise à jour: Grötzsch et Chvátal

Je n'ai pas pu résister à l'idée de colorier le vecteur 3 des graphiques de Chvátal et Grötzsch.

Le graphique de Grötsch peut être un vecteur en 3 couleurs comme suit: Placez le nœud de degré cinq sur le pôle Nord. Les 5 nœuds de degré 4 sont uniformément placés sur la même latitude, à environ 77 degrés du nord: imaginez un pentragramme peint sur l'hémisphère nord de la Terre. Les 5 nœuds restants (de degré 3) se retrouvent dans l'hémisphère sud, à environ 135 degrés du nord. Ils ont la même longitude que les 5 autres. (Je téléchargerai un dessin quand j'en aurai un, mais il est plus difficile de dessiner des lignes géodésiques dans TikZ que je ne le pensais.)

Selon un solveur SDP, Chvátal admet également un vecteur 3-coloration, mais la sortie n'est qu'un tas de vecteurs en 5 dimensions que j'ai du mal à interpréter.

(Une troisième tentative a échoué: inspiré par la construction de Yury, prenez le cycle 5 et ajoutez un sommet sommet adjacent à tous les autres. Ce graphique a le numéro chromatique 4. Mais selon mon solveur, ce n'est pas le vecteur 3-colorable.)

$\chi_v(G)$$G=C_5$

$$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$

$\chi_v(G)$$G_1$$C_5^{(1)}$$C_5^{(2)}$$C_5^{(1)}$$C_5^{(2)}$$G_2=K_5$$G$$G_1$$G_2$

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

Il s'agit ici d'un plongement du graphe de Grötzsch sur la sphère unitaire: cela correspond à une coloration vectorielle de façon évidente; par exemple, le sommet au pôle Nord est coloré avec le vecteur (0,0,1).

Le graphique de Grötsch a 3 types de nœuds. Un seul degré 5 nœuds (au nord). Cinq nœuds de degré 4 (sur l'hémisphère Nord, à égale distance de N, vous pouvez en distinguer 3). Cinq nœuds de degré 3 (sur l'hémisphère sud, à égale distance de N, vous pouvez en distinguer 3).

N est connecté à ses 5 voisins de l'hémisphère sud avec des bords verts. (Notez que le bord vert semble être incident sur les sommets de degré 4 de l'hémisphère Nord, mais c'est un artefact de l'incorporation.)

$C_5$

Enfin, une vue de dessus du pôle Sud:

Si l'on en croit mes calculs, tous les sommets voisins sont à plus de 120 degrés les uns des autres, ce qui constitue donc un vecteur-coloration valable. Le graphique de Grötzsch est chromatique 4. 11 sommets, 20 arêtes. Je suis particulièrement content de cet exemple car le coloriage vectoriel est en 3 dimensions, vous pouvez le visualiser. (Et dessinez des hyperplans aléatoires afin d'expliquer l'algorithme de coloration du graphe KMS.)