Mały wykres z odstępem między liczbą chromatyczną a liczbą chromatyczną wektorową?

Szukam małego wykresu $G$ którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, $\chi_v(G)<\chi(G)$ .

( $G$ zawiera wektor chromatycznej liczba $q$ , jeśli istnieje zadanie $x\colon V \rightarrow \mathbf R^d$ , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, $\langle x(v), x(w)\rangle \leq -1/(q-1)$ .Na przykład dla $q=3$ wystarczą wierzchołki trójkąta.)

Liczba chromatyczna wektora wykresu nie jest większa niż liczba chromatyczna: $\chi_v(G)\leq \chi(G)$ . Znane są przykłady wykresów z $\chi_v(G)=3$ $\chi(G)=n^\delta$ . (Oryginalny artykuł Karger, Motwani, Sudan [JACM, 45: 246-265] ( rękopis ) sugeruje uogólnione wykresy Knesera, nowszy artykuł wykorzystuje konstrukcję opartą na losowych wektorach jednostkowych.)

Myślę, że mam przykładowy wykres $K$ z $\chi_v(K)=4$ i $\chi(K)=8$ (na podstawie obliczeń komputerowych). Ten wykres ma 20 wierzchołków i 90 krawędzi.

Czy istnieje mniejszy przykład? Kuszącą drogą byłoby zapewnienie konkretnego wektora 3-kolorowania wykresu Chvatal lub Grötzscha, jeśli taka bestia istnieje.

( $\chi_v$ nie musi być liczbą całkowitą, ale byłoby miło. Aktualizacja: Jak wskazano poniżej, nieintegralna sprawa jest naprawdę łatwa. Dzięki.)

Aktualizacja: Grötzsch i Chvátal

Nie mogłem się powstrzymać od myślenia o wektorowym 3-kolorowaniu grafów Chvátal i Grötzsch.

Wykres Grötscha może być trójwymiarowy w następujący sposób: Umieść węzeł stopnia piątego na biegunie północnym. Węzły 5 stopni-4 są równomiernie rozmieszczone na tej samej szerokości geograficznej, około 77 stopni od północy: wyobraź sobie pentragram namalowany na północnej półkuli Ziemi. Pozostałe 5 węzłów (stopnia 3) kończy się na półkuli południowej, około 135 stopni od północy. Mają taką samą długość geograficzną jak 5 innych. (Prześlę rysunek, gdy go mam, ale trudniej jest narysować linie geodezyjne w TikZ, niż myślałem.)

Według solvera SDP, Chvátal dopuszcza również wektor 3-kolorowania, ale wyjście to tylko wiązka wektorów w 5 wymiarach, które mam trudności z interpretacją.

(Trzecia próba nie powiodła się: zainspirowana konstrukcją Yury, weź 5-cykli i dodaj wierzchołek przylegający do wszystkich pozostałych. Ten wykres ma liczbę chromatyczną 4. Ale według mojego solwera nie jest to wektor 3-kolorowy.)

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

Tutaj jest osadzenie wykresu Grötzscha na sferze jednostkowej: Odpowiada to w oczywisty sposób kolorowaniu wektora; np. wierzchołek na biegunie północnym jest zabarwiony wektorem (0,0,1).

Wykres Grötscha ma 3 typy węzłów. Węzły jednego stopnia 5 (na północy). Pięć stopni 4 węzłów (na półkuli północnej, w równej odległości od N, można dostrzec 3 z nich). Pięć stopni 3 węzłów (na półkuli południowej, w równej odległości od N, można dostrzec 3 z nich).

N jest połączony z 5 sąsiadami na półkuli południowej zielonymi krawędziami. (Zwróć uwagę, że zielona krawędź wygląda tak, jakby padała na 4-wierzchołki stopnia na półkuli północnej, ale jest to artefakt osadzania).

Patrząc z góry, można zobaczyć pentagram opisany przez węzły stopnia 4, podobnie jak osadzenie w płaszczyźnie :$C_5$

Wreszcie widok z góry bieguna południowego:

Jeśli wierzyć moim obliczeniom, wszystkie sąsiednie wierzchołki znajdują się w odległości większej niż 120 stopni względem siebie, co stanowi prawidłowy kolorowanie wektora 3. Wykres Grötzscha jest 4-chromatyczny. 11 wierzchołków, 20 krawędzi. Szczególnie cieszę się z tego przykładu, ponieważ kolorystyka wektorów jest w 3 wymiarach, abyście mogli to sobie wyobrazić. (I narysuj losowe hiperpłaszczyzny, aby wyjaśnić algorytm kolorowania grafów KMS.)