Wykres Grötzscha - Grötzsch graph
| Wykres Grötzscha | |
|---|---|
 | |
| Nazwany po | Herbert Grötzsch |
| Wierzchołki | 11 |
| Krawędzie | 20 |
| Promień | 2 |
| Średnica | 2 |
| Obwód | 4 |
| Automorfizmy | 10 ( D 5 ) |
| Liczba chromatyczna | 4 |
| Indeks chromatyczny | 5 |
| Grubość książki | 3 |
| Numer kolejki | 2 |
| Nieruchomości |
Bez trójkąta Hamiltona |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów The wykres Grötzsch jest trójkąt wolne wykres z 11 wierzchołków, 20 krawędzi, liczby chromatycznej 4 i numerem przejścia 5. Jej nazwa pochodzi od niemieckiego matematyka Herbert Grötzsch .
Wykres Grötzscha jest elementem nieskończonej sekwencji grafów bez trójkątów, z których każdy jest Mycielskianem poprzedniego grafu w sekwencji, zaczynając od grafu jednokrawędziowego; Ta sekwencja wykresów została wykorzystana przez Mycielskiego (1955) do wykazania, że istnieją grafy bez trójkątów o dowolnie dużej liczbie chromatycznej. Dlatego wykres Grötzscha jest czasami nazywany również wykresem Mycielskiego lub wykresem Mycielskiego-Grötzscha. W przeciwieństwie do późniejszych wykresów w tej sekwencji, wykres Grötzscha jest najmniejszym wykresem bez trójkątów z jego liczbą chromatyczną.
Nieruchomości
Pełna grupa automorfizmu grafu Grötzscha jest izomorficzna z dwuścienną grupą D 5 rzędu 10, grupą symetrii pięciokąta foremnego , obejmującą zarówno obroty, jak i odbicia.
Wielomian charakterystyczny wykresu Grötzsch jest
Aplikacje
Istnienie grafu Grötzscha pokazuje, że założenie płaskości jest konieczne w twierdzeniu Grötzscha, że każdy graf planarny bez trójkąta jest trójkolorowy.
Häggkvist (1981) użył zmodyfikowanej wersji grafu Grötzscha, aby obalić hipotezę Paula Erdősa i Miklosa Simonovitsa ( 1973 ) dotyczącą liczby chromatycznej grafów bez trójkątów z wysokim stopniem. Modyfikacja Häggkvista polega na zastąpieniu każdego z pięciu stopni czterech wierzchołków grafu Grötzscha zestawem trzech wierzchołków, zastąpieniu każdego z pięciu stopni trzech wierzchołków grafu Grötzscha zestawem dwóch wierzchołków i zastąpieniu pozostałych stopni- pięć wierzchołków grafu Grötzscha przez zbiór czterech wierzchołków. Dwa wierzchołki w tym rozszerzonym grafie są połączone krawędzią, jeśli odpowiadają wierzchołkom połączonym krawędzią w grafie Grötzscha. Wynikiem konstrukcji Häggkvista jest graf z liczbą 10 regularnych trójkątów bez trójkątów z 29 wierzchołkami i liczbą chromatyczną 4, obalający przypuszczenie, że nie ma grafu n -wierzchołkowego bez trójkątów 4-chromatycznych, w którym każdy wierzchołek ma więcej niż n /3 sąsiadów .
Powiązane wykresy
Udziały wykres Grötzsch kilka właściwości z wykresu Clebsch , a odległość-przechodni wykresie z 16 wierzchołków i 40 krawędzie, zarówno wykres Grötzsch a wykres Clebsch mają trójkątny wolny i cztery chromatycznej, a żaden z nich nie ma żadnego sześciokrotnie wierzchołek wywołanego ścieżki . Własności te są bliskie wystarczającej do scharakteryzowania tych wykresów: wykres Grötzscha jest indukowanym podgrafem wykresu Clebscha, a każdy czterochromatyczny wolny wykres bez trójkąta jest podobnie indukowanym podgrafem wykresu Clebscha, który z kolei zawiera wykres Grötzscha wykres jako podgraf indukowany. Wykres Chvátal kolejny niewielki trójkątny wolny 4-chromatycznej wykresu. Jednak w przeciwieństwie do grafu Grötzscha i grafu Clebscha, graf Chvatala ma ścieżkę indukowaną sześcioma wierzchołkami.
Uwagi
Bibliografia
- Chvátal, Vašek (1974), "Minimalizm grafu Mycielskiego", Wykresy i kombinatoryka (Proc. Capital Conf., George Washington Univ., Waszyngton, DC, 1973) , Berlin: Uwagi do wykładu z matematyki, t. 406, Springer-Verlag, s. 243–246, MR 0360330
- Erdős, P. ; Simonovits, M. (1973), „Na problem walencyjny w teorii grafów ekstremalnych”, Discrete Mathematics , 5 (4): 323-334, doi : 10.1016/0012-365X(73)90126-X , MR 0342429
- Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109–120, MR 0116320
- Häggkvist, R. (1981), „Nieparzyste cykle o określonej długości w grafach niedwuczęściowych”, teoria grafów (Cambridge, 1981) , str. 89-99, MR 0671908
- Mycielski, Jan (1955), „Sur le coloriage des graphs”, Colloq. Matematyka. , 3 (2): 161–162, doi : 10.4064/cm-3-2-161-162 , MR 0069494
- Randeratha, Berta; Schiermeyera, Ingo; Tewes, Meike (2002), "Trzy-kolorowalność i zabronione podgrafy. II. Algorytmy wielomianowe", Matematyka dyskretna , 251 (1-3): 137-153, doi : 10.1016/S0012-365X(01)00335-1 , MR 1904597