Przypuszczenie Hadwigera (teoria grafów) - Hadwiger conjecture (graph theory)

Zobacz także: przypuszczenie Hadwigera (geometria kombinatoryczna)
Nierozwiązany problem w matematyce :

Czy każdy wykres z liczbą chromatyczną ma kompletny wykres -vertex jako pomniejszy ?

(więcej nierozwiązanych problemów z matematyki)
Wykres, który wymaga czterech kolorów w dowolnym kolorze i czterech połączonych podgrafów, które po skróceniu tworzą kompletny wykres, ilustrujący przypadek k  = 4 hipotezy Hadwigera

W teorii grafów The Hadwiger przypuszczać , że jeśli G jest loopless i ma drobne następnie jego chromatyczne liczba spełnia . Wiadomo, że to prawda dla . Przypuszczenie jest uogólnieniem twierdzenia o czterech kolorach i jest uważane za jeden z najważniejszych i najtrudniejszych otwartych problemów w tej dziedzinie.

Mówiąc bardziej szczegółowo, jeśli wszystkie odpowiednie barwniki o o nieukierunkowane wykres G zastosowania K lub więcej kolorów, wówczas można znaleźć k rozłącznych połączone subgraphs z G , tak że każda subgraph jest połączony z krawędzią każdej innej podgrafu. Zawężenie krawędzi w każdym z tych podgrafów tak, że każdy podgraf zwija się do pojedynczego wierzchołka, daje kompletny graf K k na k wierzchołkach jako mniejszy od G .

To przypuszczenie, daleko idące uogólnienie problemu czterech kolorów , zostało postawione przez Hugo Hadwigera w 1943 roku i nadal pozostaje nierozwiązane. Bollobás, Catlin i Erdős (1980) nazywają to „jednym z najgłębszych nierozwiązanych problemów w teorii grafów”.

Formy równoważne

Równoważna forma hipotezy Hadwigera ( przeciwdodatnia do formy podanej powyżej) jest taka, że ​​jeśli nie ma sekwencji skróconych krawędzi (z których każde łączy dwa punkty końcowe jakiejś krawędzi w jeden superwierzchołek), to daje graf G do pełnego grafu K k , to G musi mieć kolorowanie wierzchołka z k  − 1 kolorami.

Zauważ, że przy minimalnym k- kolorowaniu dowolnego grafu G , skrócenie każdej klasy koloru pokolorowania do pojedynczego wierzchołka da kompletny graf K k . Jednak ten proces skrócenia nie daje w wyniku skrócenia G, ponieważ (z definicji) nie ma krawędzi między dowolnymi dwoma wierzchołkami w tej samej klasie kolorów, a zatem skrócenie nie jest skróceniem krawędzi (co jest wymagane w przypadku mniejszych). Hipoteza Hadwigera mówi, że istnieje inny sposób prawidłowego skontraktowania krawędzi zbiorów wierzchołków do pojedynczych wierzchołków, tworząc kompletny graf K k , w taki sposób, że wszystkie skontraktowane zbiory są połączone.

Jeżeli K K oznacza rodzinę wykresów mających tę właściwość, że wszystkie nieletnich wykresów na F K może być ( k  - 1) -colored, to wynika z Robertson-Seymour twierdzenie , że K K można scharakteryzować przez skończony zestaw zabroniony nieletni . Przypuszczenie Hadwigera jest takie, że ten zbiór składa się z jednego zakazanego małoletniego, K k .

Liczba Hadwigera h ( G ) grafu G jest rozmiarem k największego pełnego grafu K k , który jest mniejszą od G (lub równoważnie można ją otrzymać przez skrócenie krawędzi G ). Jest znany także jako liczby Skurcz klik o G . Hadwiger przypuszczenie można stwierdzić w prostej postaci algebraicznej Ď ( G ) ≤  H ( G ), w którym χ ( G ) oznacza liczbę chromatyczną o G .

Przypadki szczególne i wyniki częściowe

Przypadek k  = 2 jest trywialny: graf wymaga więcej niż jednego koloru wtedy i tylko wtedy, gdy ma krawędź, a ta krawędź sama jest K 2 minor. Przypadek k  = 3 też jest łatwy: grafy wymagające trzech kolorów to grafy niedwudzielnościowe , a każdy graf niedwudzielny ma cykl nieparzysty , który można skrócić do 3 cykli, czyli K 3 minor.

W tej samej pracy, w której przedstawił hipotezę, Hadwiger udowodnił jej prawdziwość dla k  ≤ 4. Grafami bez K 4 minor są grafy szeregowo-równoległe i ich podgrafy. Każdy graf tego typu ma wierzchołek z co najwyżej dwiema krawędziami padającymi; każdy taki graf można 3-kolorować, usuwając jeden taki wierzchołek, rekurencyjnie kolorując pozostały graf, a następnie dodając z powrotem i pokolorując usunięty wierzchołek. Ponieważ usunięty wierzchołek ma co najwyżej dwie krawędzie, jeden z trzech kolorów będzie zawsze dostępny do pokolorowania go po ponownym dodaniu wierzchołka.

Prawda przypuszczenia dla k  = 5 implikuje twierdzenie o czterech kolorach : ponieważ, jeśli przypuszczenie jest prawdziwe, każdy graf wymagający pięciu lub więcej kolorów miałby K 5 minor i byłby (według twierdzenia Wagnera ) niepłaski. Klaus Wagner udowodnił w 1937 roku, że przypadek k  = 5 jest w rzeczywistości równoważny twierdzeniu o czterech kolorach i dlatego teraz wiemy, że to prawda. Jak pokazał Wagner, każdy graf, który nie ma K 5 minor, można rozłożyć za pomocą sum klik na części, które są albo płaskie, albo 8-wierzchołkowe drabiny Möbiusa , a każdy z tych kawałków może być czterokolorowy niezależnie od siebie, więc 4-zabarwienia o K 5 -minor wolne wykresu wynika z 4-zabarwienia każdego z płaskich elementów.

Robertson, Seymour i Thomas (1993) udowodnili przypuszczenie dla k  = 6, również używając twierdzenia o czterech kolorach; ich praca z tym dowodem zdobyła nagrodę Fulkersona w 1994 roku . Z ich dowodu wynika, że grafy osadzane bezłącznie , trójwymiarowy odpowiednik grafów planarnych, mają liczbę chromatyczną co najwyżej pięć. Z powodu tego wyniku wiadomo, że przypuszczenie jest prawdziwe dla k  ≤ 6, ale pozostaje nierozwiązane dla wszystkich k  > 6.

Dla k  = 7 znane są niektóre wyniki cząstkowe: każdy wykres 7-chromatyczny musi zawierać albo K 7 minor, albo zarówno K 4,4 minor, jak i K 3,5 minor.

Każdy graf G ma wierzchołek z krawędziami przypadającymi co najwyżej O( h ( G )  √ log h ( G ) ), z czego wynika, że algorytm zachłannego kolorowania , który usuwa ten niski wierzchołek, koloruje pozostały graf, a następnie dodaje cofnij usunięty wierzchołek i pokoloruj go, pokoloruje dany wykres kolorami O( h ( G )  √ log h ( G ) ).

W latach 80. Alexander V. Kostochka i Andrew Thomason niezależnie udowodnili, że każdy wykres bez -minorów ma średni stopień i dlatego można go pokolorować za pomocą kolorów. Ten wynik został później poprawiony przez Sergeya Norina, Zi-Xia Song i Luke'a Postle'a do kolorów dla dowolnych . W 2020 roku Postle ogłosił kolejne ulepszenie -kolorowalności dla wykresów bez -minorów.

Van der Zypen (2012) skonstruował graf H z χ(H) =  ω, ale bez K ω minor, wykazując, że przypuszczenie nie obowiązuje dla grafów o przeliczalnie nieskończonej liczbie zabarwienia.

Uogólnienia

György Hajós przypuszczał, że hipotezę Hadwigera można wzmocnić do podpodziałów, a nie mniejszych: to znaczy, że każdy graf o liczbie chromatycznej k zawiera podpodział pełnego grafu K k . Hipoteza Hajósa jest prawdziwa dla k ≤ 4, ale Catlin (1979) znalazł kontrprzykłady dla tej wzmocnionej hipotezy dla k  ≥ 7; sprawy k  = 5 i k  = 6 pozostają otwarte. Erdős i Fajtlowicz (1981) zaobserwowali, że hipoteza Hajósa nie sprawdza się w przypadku grafów losowych : dla dowolnego ε > 0, w granicy, gdy liczba wierzchołków n dąży do nieskończoności, prawdopodobieństwo zbliża się do takiego, jakie ma losowy graf n -wierzchołkowy liczba chromatyczna ≥ (1/2 − ε) n  / log 2  n , oraz że największy podział kliki ma co najwyżej cn 1/2 wierzchołków dla pewnej stałej c . W tym kontekście warto zauważyć, że prawdopodobieństwo zbliża się również do tego, że losowy graf n -wierzchołkowy ma liczbę Hadwigera większą lub równą jego liczbie chromatycznej, więc hipoteza Hadwigera obowiązuje dla grafów losowych z dużym prawdopodobieństwem; dokładniej, liczba Hadwigera jest z dużym prawdopodobieństwem a stała razy n / √ log  n .

Borowiecki (1993) zapytał, czy przypuszczenie Hadwigera można rozszerzyć o kolorowanie list . Dla k  ≤ 4, każdy graf z listą o liczbie chromatycznej k ma k- wierzchołkową klikę mniejszą. Jednak maksymalna liczba chromatyczna listy grafów planarnych wynosi 5, a nie 4, więc rozszerzenie nie powiedzie się już dla grafów K 5 -minor-free. Bardziej ogólnie, dla każdego t  ≥ 1 istnieją grafy, których liczba Hadwigera wynosi 3 t  + 1 i których liczba chromatyczna listy wynosi 4 t  + 1.

Gerards i Seymour przypuszczali, że każdy graf G o liczbie chromatycznej k ma pełny graf K k jako nieparzysty molowy . Taką strukturę można przedstawić jako rodzinę k wierzchołków-rozłącznych poddrzew G , z których każde jest dwukolorowe, tak że każda para poddrzew jest połączona monochromatyczną krawędzią. Chociaż grafy bez nieparzystego K k mniejszego niekoniecznie są rzadkie , obowiązuje dla nich podobna górna granica, jak w przypadku standardowej hipotezy Hadwigera: graf bez nieparzystego K k mniejszego ma liczbę chromatyczną χ ( G ) = O(k  √ log  k ).

Nakładając dodatkowe warunki na G , może być możliwe udowodnienie istnienia większej liczby nieletnich niż K k . Jednym z przykładów jest twierdzenie Snarka , że każdy graf sześcienny wymagający czterech kolorów w dowolnym kolorowaniu krawędzi ma graf Petersena jako drugorzędny, przypuszczony przez WT Tutte i ogłoszony jako udowodniony w 2001 roku przez Robertsona, Sandersa, Seymoura i Thomasa.

Uwagi

Bibliografia