numer Hadwigera

Wykres z czterema połączonymi podgrafami, które po skróceniu tworzą pełny graf. Zgodnie z twierdzeniem Wagnera nie ma pięciu pełnych wierzchołków mniejszych , więc jego liczba Hadwigera wynosi dokładnie cztery.

W teorii grafów liczba Hadwigera nieskierowanego grafu G jest wielkością największego kompletnego grafu , jaki można uzyskać przez skrócenie krawędzi grafu G. Równoważnie liczba Hadwigera h ( G ) jest największą liczbą n , dla której pełny wykres K _n jest mniejszy od G , mniejszy wykres uzyskany z G przez skurcze krawędzi oraz usuwanie wierzchołków i krawędzi. Liczba Hadwigera jest również znana jako liczba kliki kontrakcji G lub stopień homomorfizmu G . Jej nazwa pochodzi od nazwiska Hugo Hadwigera , który wprowadził ją w 1943 r. w połączeniu z hipotezą Hadwigera , zgodnie z którą liczba Hadwigera jest zawsze co najmniej tak duża, jak liczba chromatyczna G.

Grafy, które mają liczbę Hadwigera co najwyżej cztery, zostały scharakteryzowane przez Wagnera (1937) . Wykresy z dowolną skończoną granicą na liczbie Hadwigera są rzadkie i mają małą liczbę chromatyczną. Określenie liczby Hadwigera wykresu jest NP-trudne , ale wykonalne dla ustalonych parametrów .

Wykresy z małą liczbą Hadwigera

Graf G ma liczbę Hadwigera co najwyżej dwa wtedy i tylko wtedy , gdy jest lasem , ponieważ kompletny podrzędny z trzema wierzchołkami można utworzyć tylko przez skrócenie cyklu w G .

Wykres ma liczbę Hadwigera co najwyżej trzy wtedy i tylko wtedy, gdy jego szerokość drzewa wynosi co najwyżej dwa, co jest prawdziwe wtedy i tylko wtedy, gdy każdy z jego połączonych ze sobą składników jest grafem szeregowo-równoległym .

Klika-suma dwóch grafów planarnych i wykresu Wagnera, tworząca większy graf z numerem cztery Hadwigera.

Twierdzenie Wagnera , które charakteryzuje grafy planarne za pomocą ich zabronionych drugorzędnych , implikuje, że grafy planarne mają liczbę Hadwigera co najwyżej cztery. W tym samym artykule, który dowiódł tego twierdzenia, Wagner (1937) również dokładniej scharakteryzował grafy o liczbie Hadwigera co najwyżej cztery: są to grafy, które można utworzyć za pomocą operacji sumowania klików , które łączą grafy planarne z grafem Wagnera o ośmiu wierzchołkach .

Grafy z liczbą Hadwigera co najwyżej pięć obejmują grafy wierzchołkowe i grafy, które można osadzić bez powiązań , z których oba mają pełny graf K ₆ wśród zabronionych drugorzędnych.

Rzadkość

$_$ z n i k ma _ Ta $granica$ dla każdego istnieją grafy z liczbą , które mają Jeśli graf G ma liczbę Hadwigera k , to wszystkie jego podgrafy również mają co najwyżej liczbę Hadwigera k , a wynika z tego, że G musi mieć degenerację ${\ Displaystyle O (k {\ sqrt {\ log k}})}$ . Dlatego grafy z ograniczoną liczbą Hadwigera są grafami rzadkimi .

Kolorowanie

Hipoteza Hadwigera stwierdza, że ​​liczba Hadwigera jest zawsze co najmniej tak duża jak liczba chromatyczna G . Oznacza to, że każdy graf o liczbie Hadwigera k powinien mieć graf kolorowany co najwyżej k kolorami. Przypadek k = 4 jest równoważny (według charakterystyki grafów z tą liczbą Hadwigera przez Wagnera) czterokolorowemu twierdzeniu o kolorowaniu grafów planarnych , a hipoteza została również udowodniona dla k ≤ 5 , ale pozostaje nieudowodnione dla większych wartości k .

$Hadwigera$ najwyżej k można pokolorować za pomocą przy użyciu .

Złożoność obliczeniowa

Sprawdzenie, czy liczba Hadwigera danego grafu jest co najmniej zadaną wartością k jest NP-zupełne , z czego wynika, że ​​wyznaczenie liczby Hadwigera jest NP-trudne . Jednak problem można rozwiązać za pomocą ustalonych parametrów : istnieje algorytm znajdowania największej kliki mniejszej w czasie, który zależy tylko wielomianowo od rozmiaru wykresu, ale wykładniczo w h ( G ) . Ponadto algorytmy czasu wielomianowego mogą przybliżać liczbę Hadwigera znacznie dokładniej niż najlepsze przybliżenie czasu wielomianowego (zakładając P ≠ NP ) do rozmiaru największego pełnego podgrafu .

Pojęcia pokrewne

Achromatyczna liczba grafu G jest wielkością największej kliki, jaką można utworzyć przez skrócenie rodziny niezależnych zbiorów w G .

Niepoliczalne nieletnie kliki na nieskończonych grafach można scharakteryzować za pomocą przystani , które formalizują strategie unikania w niektórych grach pościgowo-unikających : jeśli liczba Hadwigera jest niepoliczalna, to jest równa największemu rzędowi przystani na wykresie.

Każdy graf o liczbie Hadwigera k ma co najwyżej n 2 ^{O ( k log(log k ))} klik (pełne podgrafy).

Halin (1976) definiuje klasę parametrów grafu, które nazywa S -funkcjami, do których należy liczba Hadwigera. Te funkcje od grafów do liczb całkowitych muszą być zerowe na grafach bez krawędzi , być drugorzędne-monotoniczne , zwiększać się o jeden, gdy dodawany jest nowy wierzchołek, który sąsiaduje ze wszystkimi poprzednimi wierzchołkami, i przyjmować większą wartość z dwóch podgrafy po obu stronach separatora kliki . Zbiór wszystkich takich funkcji tworzy kompletną kratę w ramach operacji elementarnej minimalizacji i maksymalizacji. Dolnym elementem tej sieci jest liczba Hadwigera, a górnym elementem jest szerokość drzewa .

Notatki

• Alon, Noga ; Lingas, Andrzej; Wahlen, Martin (2007), „Przybliżanie problemów z homeomorfizmem maksymalnej kliki i niektórych podgrafów” (PDF) , Teoretyczna informatyka , 374 (1–3): 149–158, doi : 10.1016/j.tcs.2006.12.021 .
• Bollobás, B. ; Catlin, Pensylwania; Erdős, Paul (1980), „Przypuszczenie Hadwigera jest prawdziwe dla prawie każdego wykresu” (PDF) , European Journal of Combinatorics , 1 : 195–199, doi : 10.1016/s0195-6698 (80) 80001-1 .
• Eppstein, David (2009), „Znajdowanie nieletnich dużej kliki jest trudne”, Journal of Graph Algorithms and Applications , 13 (2): 197–204, arXiv : 0807.0007 , doi : 10.7155/jgaa.00183 .
• Fomin, Fedor V.; Oum, Sang-il ; Thilikos, Dimitrios M. (2010), „Rang-width and tree-width of H -moll-free graphs”, European Journal of Combinatorics , 31 (7): 1617–1628, arXiv : 0910,0079 , doi : 10,1016/j. ejc.2010.05.003 .
• Hadwiger, Hugo (1943), „Über eine Klassifikation der Streckenkomplexe”, Vierteljschr. Naturforsch. Ges. Zurych , 88 : 133–143 .
•   Halin, Rudolf (1976), „ S -funkcje dla grafów”, J. Geometry , 8 (1–2): 171–186, doi : 10.1007/BF01917434 , MR 0444522 .
• Kostochka, AV (1984), „Dolna granica liczby wykresów Hadwigera według ich średniego stopnia”, Combinatorica , 4 (4): 307–316, doi : 10.1007 / BF02579141 .
•   Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (1991), „Z wyłączeniem nieskończonych nieletnich”, Discrete Mathematics , 95 (1–3): 303–319, doi : 10.1016/0012-365X (91) 90343-Z , MR 1141945 .
• Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (1993a), „Przypuszczenie Hadwigera dla grafów wolnych od K ₆ ” (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007 / BF01202354 .
•   Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993b), „Bezpołączeniowe osadzenie wykresów w przestrzeni 3”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1164063 .
• Thomason, Andrew (2001), „Funkcja ekstremalna dla kompletnych nieletnich”, Journal of Combinatorial Theory , Seria B, 81 (2): 318–338, doi : 10.1006/jctb.2000.2013 .
• Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann. , 114 : 570–590, doi : 10.1007/BF01594196 .