Przejdźmy teraz do rozważań topologicznych związanych z liczbą chromatyczną. Tematyka ta wywodzi się od największego polskiego osiągnięcia w teorii grafów - twierdzenia Kuratowskiego, charakteryzującego grafy planarne. Przypomnijmy definicje grafu planarnego:

Definicja : Graf jest planarny, jeśli można go “narysować” na płaszczyźnie tak, by krawędzie nie przecinały się poza punktami będącymi ich wpólnymi końcami (wierzchołkami).

Na przykład graf pełny K₄ jest planarny, ale ani graf K₅, ani K_3,3 takie nie są (są to 2 najmniejsze grafy nie planarne). Oczywiscie jeśli graf zawiera jako podgraf K₅ lub K_3,3 to nie jest on planarny.

Definicja : Rozszeżeniem topologicznym grafu G nazywamy każdy graf otrzymany z grafu G poprzez przez umieszczenie, w dowolnej liczbie wierzchołków stopnia 2.na jego krawędziach.

Inaczej mówiac zastepuje się niektóre (lub wszystkie) krawędzie grafu ścieżkami o dowolnych długościach. Rozszeżenie topologiczne grafu G będziemy oznaczać przez TG. Graf będący rozszeżeniem grafu pełnego będziemy nazywać kliką topologiczną. Nietrudno zauważyć, że graf G jest planarny wtedy i tylko wtedy gdy graf TG jest planarny. W szczególności, jeśli graf G zawiera TK₅ lub TK_3,3, to graf G nie jest planarny. Kazimierz Kuratowski wykazał że są to jedyne dwa powody, dla których graf G może być nieplanarny.

Twierdzenie (Kuratowski, 1930) : Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera ani TK₅, ani TK_3,3

Sugerując się tym twierdzeniem Hajós postawił w 1961 roku następująco hipotezę

Hipoteza Hajósa : Jeśli χ(G) = k, to G ⊇ TK_3,3.

Przypadki k = 1,2,3 są trywialne. Przypadek k = 4 udowodnił jeszcze przed powstaniem hipotezy Dirac (1952).W 1979 Catlin skonstruował przykłady dla k ≥ 7, natomiast Erdös i Fajtlowicz, korzystając z teorii grafów losowych, udowodnili, że asymptotycznie prawie wszystkie grafy są kontrprzykładami (choć nie byli w stanie skonstruować żadnego z nich).

Podobną choć ostrożniejszą hipotezę postawił w 1943 roku Hadwiger. Zamiast pojęcia rozszeżenia topologicznego grafu użyl on pojęcia ściągnięcia grafu. Nie trudno zauważyć, że jeśli graf G jest rozszeżeniem topologicznym grafu H, to graf H jest ściągnięciem grafu G, ale odwrotnie być nie musi. Twierdzenie Wagnera i hipoteza Hadwigera brzmią następująco:

Twierdzenie 2 (Wagner, 1937) : Graf jest planarny wtedy, i tylko wtedy gdy nie zawiera ani grafu ściągalnego do K₅, ani podgrafu ściągalnego do K_3,3

Hipoteza Hadwigera (1943) : Jeśli χ(G) = k, to G zawiera podgraf ściągalny do K_k

Hipoteza Hadwigera jest słabsza od hipotezy Hajósa. Prawdziwość hipotezy Hajósa dla k = 3,4 implikuje natychmiast prawdziwosc hipotezy Hadwigera w tych dwóch przypadkach. W 1937 roku Wagner pokazał, że hipoteza Hadwigera dla k = 5 jest równoważna Hipotezie Czterech Kolorów

Hipoteza Czterech Kolorów (1852) : Jesli G jest grafem planarnym to χ(G) ≤ 4

Zatem, z chwilą udowodnienia tej ostatniej w 1976 roku przez Appela i Hakena, hipoteza Hadwigera stała się prawdziwa dla wszystkich k ≤ 5. W 1980 Bollobas, Catlin i Erdös pokazali ze spełniają je samyptotycznie prawie wszystkie grafy. Robertson, Seymour i Thomas udowodnili hipoteze Hadwigera dla k = 6.

Literatura