Gráfico pequeño con espacio entre el número cromático y el cromático vectorial?

Estoy buscando un pequeño gráfico $G$ cuyo número cromático vectorial es menor que el número cromático, $\chi_v(G)<\chi(G)$ .

( $G$ tiene vector número cromática $q$ si hay una asignación $x\colon V \rightarrow \mathbf R^d$ , donde intuitivamente los vectores asociados con vértices vecinos están muy separados El requisito es. $\langle x(v), x(w)\rangle \leq -1/(q-1)$ . Por ejemplo, para $q=3$ , los vértices de un triángulo son suficientes.)

El número cromático vectorial de un gráfico no es mayor que el número cromático: $\chi_v(G)\leq \chi(G)$ . Se conocen ejemplos de gráficos con $\chi_v(G)=3$ $\chi(G)=n^\delta$ . (El artículo original de Karger, Motwani, Sudán [JACM, 45: 246-265] ( manuscrito ) sugiere gráficos Kneser generalizados, un artículo más reciente utiliza una construcción basada en vectores unitarios aleatorios.

Creo que tengo un ejemplo de gráfico $K$ con $\chi_v(K)=4$ y $\chi(K)=8$ (basado en el cálculo de la computadora). Este gráfico tiene 20 vértices y 90 aristas.

¿Hay un ejemplo más pequeño? Una avenida tentadora sería proporcionar un vector concreto de 3 colores del gráfico de Chvatal o Grötzsch, si tal bestia existe.

( $\chi_v$ no necesita ser un número entero, pero sería bueno. Actualización: Como se señala a continuación, el caso no integral es realmente fácil. Gracias.)

Actualización: Grötzsch y Chvátal

No pude resistirme a pensar en el vector 3 para colorear los gráficos de Chvátal y Grötzsch.

El gráfico de Grötsch puede ser un vector de 3 colores de la siguiente manera: Coloque el nodo de grado cinco en el polo norte. Los 5 nodos de grado 4 se colocan de manera uniforme en la misma latitud, a unos 77 grados del norte: imagine un pentragrama pintado en el hemisferio norte de la Tierra. Los 5 nodos restantes (de grado 3) terminan en el hemisferio sur, a unos 135 grados del norte. Tienen la misma longitud que los otros 5. (Cargaré un dibujo cuando tenga uno, pero es más difícil dibujar líneas geodésicas en TikZ de lo que pensaba).

Según un solucionador de SDP, Chvátal también admite un vector de 3 colores, pero la salida es solo un conjunto de vectores en 5 dimensiones que tengo dificultades para interpretar.

(Un tercer intento falló: inspirado por la construcción de Yury, tome el ciclo 5 y agregue un vértice de vértice adyacente a todos los demás. Este gráfico tiene el número cromático 4. Pero según mi solucionador no es el vector de 3 colores).

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

Aquí es una incrustación del gráfico de Grötzsch en la esfera de la unidad: esto corresponde a un color vectorial de la manera obvia; por ejemplo, el vértice en el polo norte se colorea con el vector (0,0,1).

El gráfico de Grötsch tiene 3 tipos de nodos. Un solo grado 5 nodos (en el norte). Cinco nodos de grado 4 (en el hemisferio norte, equidistante a N, puede distinguir 3 de ellos). Cinco nodos de grado 3 (en el hemisferio sur, equidistantes a N, puede distinguir 3 de ellos).

N está conectado a sus 5 vecinos en el hemisferio sur con bordes verdes. (Tenga en cuenta que el borde verde parece incidir en los vértices de grado 4 en el hemisferio norte, pero eso es un artefacto de la incrustación).

$C_5$

Finalmente, una vista desde arriba del polo sur:

Si hay que creer en mis cálculos, todos los vértices vecinos están a más de 120 grados entre sí, por lo que esto constituye un vector válido de 3 colores. El gráfico de Grötzsch es 4-cromático. 11 vértices, 20 aristas. Estoy particularmente contento con este ejemplo porque el color del vector está en 3 dimensiones, para que pueda visualizarlo. (Y dibuje hiperplanos aleatorios para explicar el algoritmo de coloración del gráfico KMS).