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

12

Szukam małego wykresu G którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, χv(G)<χ(G) .

( G zawiera wektor chromatycznej liczba q , jeśli istnieje zadanie x:VRd , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, x(v),x(w)1/(q1) .Na przykład dla q=3 wystarczą wierzchołki trójkąta.)

Liczba chromatyczna wektora wykresu nie jest większa niż liczba chromatyczna: χv(G)χ(G) . Znane są przykłady wykresów z χv(G)=3 χ(G)=nδ . (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 χv(K)=4 i χ(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.

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

Thore Husfeldt
źródło
1
Czy możesz podać link lub definicję wektorowej liczby chromatycznej?
Suresh Venkat
4
χv(C5)=5<3=χ(C5)C5C5Gχv(G)χ(G)

Odpowiedzi:

7

χv(G)G=C5

χv(C5)=5<3=χ(C5).[Lovász]

χv(G)G1C5(1)C5(2)C5(1)C5(2)G2=K5GG1G2

χ(G)=max(χ(G1),χ(G2))=χ(G1)=6.χv(G)=max(χv(G1),χv(G2))=max(25,5)=5.
Yury
źródło
3

Tutaj jest osadzenie wykresu Grötzscha na sferze jednostkowej: wprowadź opis zdjęcia tutaj 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 :C5wprowadź opis zdjęcia tutaj

Wreszcie widok z góry bieguna południowego: wprowadź opis zdjęcia tutaj

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

Thore Husfeldt
źródło