Przypuszczenie Heawooda
W teorii grafów hipoteza Heawooda lub twierdzenie Ringela-Youngsa podaje dolną granicę liczby kolorów niezbędnych do pokolorowania grafów na powierzchni danego rodzaju . Dla powierzchni rodzaju 0, 1, 2, 3, 4, 5, 6, 7, ... wymagana liczba kolorów to 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS : A000934 , liczba chromatyczna lub liczba Heawooda.
Hipoteza została sformułowana w 1890 roku przez Percy'ego Johna Heawooda i udowodniona w 1968 roku przez Gerharda Ringela i Teda Youngsa . Jeden przypadek, nieorientowana butelka Kleina , okazał się wyjątkiem od ogólnej formuły. Potrzebne było zupełnie inne podejście do znacznie starszego problemu znalezienia liczby kolorów potrzebnej dla płaszczyzny lub kuli , rozwiązanego w 1976 roku jako twierdzenie o czterech kolorach Hakena i Appela . Na kuli dolna granica jest łatwa, podczas gdy dla wyższych rodzajów górna granica jest łatwa i została udowodniona w oryginalnym krótkim artykule Heawooda, który zawierał przypuszczenie. Innymi słowy, Ringel, Youngs i inni musieli skonstruować skrajne przykłady dla każdego rodzaju g = 1,2,3,.... Jeśli g = 12s + k, rodzaje dzielą się na 12 przypadków zgodnie z k = 0,1, 2,3,4,5,6,7,8,9,10,11. Dla uproszczenia załóżmy, że przypadek k został ustalony, jeśli tylko skończona liczba g postaci 12s + k jest wątpliwa. Następnie lata, w których dwanaście spraw zostało rozstrzygniętych i przez kogo, są następujące:
- 1954, Ringel: przypadek 5
- 1961, Ringel: przypadki 3,7,10
- 1963, Terry, Welch, Youngs: przypadki 0,4
- 1964, Gustin, Youngs: przypadek 1
- 1965, Gustin: przypadek 9
- 1966, Młodzi: przypadek 6
- 1967, Ringel, Youngs: przypadki 2,8,11
Ostatnie siedem sporadycznych wyjątków zostało rozstrzygniętych w następujący sposób:
- 1967, Mayer: sprawy 18, 20, 23
- 1968, Ringel, Youngs: przypadki 30, 35, 47, 59 i hipoteza została udowodniona.
Oświadczenie formalne
Percy John Heawood wysunął w 1890 r. przypuszczenie, że dla danego rodzaju g > 0 minimalna liczba kolorów potrzebna do pokolorowania wszystkich grafów narysowanych na orientowalnej powierzchni tego rodzaju (lub równoważnie do pokolorowania obszarów dowolnego podziału powierzchni na obszary o prostym połączeniu ) jest dany przez
gdzie jest funkcją podłogi .
Zastępując rodzaj cechą Eulera , otrzymujemy formułę obejmującą zarówno przypadki orientowalne, jak i nieorientowalne,
Zależność ta zachodzi, jak wykazali Ringel i Youngs, dla wszystkich powierzchni z wyjątkiem butelki Kleina . Philip Franklin (1930) udowodnił, że butelka Kleina wymaga co najwyżej 6 kolorów, a nie 7, jak przewiduje wzór. Wykres Franklina można narysować na butelce Kleina w sposób, który tworzy sześć wzajemnie przylegających regionów, pokazując, że ta granica jest ścisła.
Górna granica, udowodniona w oryginalnym krótkim artykule Heawooda, jest oparta na zachłannym algorytmie kolorowania. Manipulując charakterystyką Eulera, można pokazać, że każdy wykres osadzony na danej powierzchni musi mieć co najmniej jeden wierzchołek o stopniu mniejszym niż podana granica. Jeśli usunie się ten wierzchołek i pokoloruje resztę wykresu, niewielka liczba krawędzi padających na usunięty wierzchołek gwarantuje, że można go ponownie dodać do wykresu i pokolorować bez zwiększania potrzebnej liczby kolorów poza granicę. W drugą stronę dowód jest trudniejszy i polega na pokazaniu, że w każdym przypadku (z wyjątkiem butelki Kleina) pełny wykres o liczbie wierzchołków równej podanej liczbie kolorów można osadzić na powierzchni.
Przykład
Torus ma g = 1, więc χ = 0. Dlatego, jak stwierdza wzór, każdy podział torusa na regiony można pokolorować przy użyciu co najwyżej siedmiu kolorów . Ilustracja przedstawia podział torusa, w którym każdy z siedmiu regionów sąsiaduje ze sobą; ten podział pokazuje, że granica liczby siedmiu kolorów jest w tym przypadku ciasna. Granica tego podziału tworzy osadzenie wykresu Heawooda na torusie.
- Franklin, P. (1934). „Problem z sześcioma kolorami”. MIT Journal of Mathematics and Physics . 13 (1–4): 363–379. doi : 10.1002/sapm1934131363 . hdl : 2027/mdp.39015019892200 .
- Heawood, PJ (1890). „Twierdzenie o kolorze mapy”. Kwartalnik Matematyki . 24 : 332–338.
- Ringel, G .; Młodzi, JWT (1968). „Rozwiązanie problemu kolorowania mapy Heawood” . Proceedings of the National Academy of Sciences of the United States of America . 60 (2): 438–445. Bibcode : 1968PNAS...60..438R . doi : 10.1073/pnas.60.2.438 . MR 0228378 . PMC 225066 . PMID 16591648 .