Szukam małego wykresu którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, .
( zawiera wektor chromatycznej liczba , jeśli istnieje zadanie , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, .Na przykład dla wystarczą wierzchołki trójkąta.)
Liczba chromatyczna wektora wykresu nie jest większa niż liczba chromatyczna: . Znane są przykłady wykresów z . (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 z i (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.
( 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.)
źródło
Odpowiedzi:
źródło
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 :C5
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.)
źródło