Kolorowanie płaskich wykresów

21

Rozważ zestaw płaskich wykresów, w których wszystkie ściany wewnętrzne są trójkątami. Jeśli jest punkt wewnętrzny nieparzystego stopnia, wykres nie może być trójkolorowy. Jeśli każdy punkt wewnętrzny ma równy stopień, czy zawsze może być trójkolorowy? Idealnie chciałbym mały kontrprzykład.

graph-theory co.combinatorics graph-colouring Lance Fortnow
źródło

Odpowiedzi:

25

Tak, jest to następstwo twierdzenia o trzech kolorach, patrz na dole tutaj: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
źródło
1
Dzięki. Czy masz referencję na dowód?
Lance Fortnow
3
Możesz spojrzeć na te dwa artykuły: google.com/… i google.com/…
Joseph Malkevitch
6
Aby dodać do odniesień Malkevitcha: równoważność trójkolorowości, a nawet stopnia dla płaskich triangulacji jest zwykle przypisywana PJ Heawoodowi, „Twierdzeniu o czterokolorowej mapie”. Kwartalnik J. Pure Appl. Matematyka 29: 270–285, 1898. Jednak dokumenty, do których nawiązał Malkevitch, mają więcej do powiedzenia na temat tego przypisania.
David Eppstein,
6
Wniosek ten nie jest wspomniany w notatkach Hulla, tylko samo twierdzenie o trzech kolorach. Ale z 3 połączonego wykresu G z trójkątnymi ścianami wewnętrznymi, a nawet wewnętrznymi wierzchołkami, można utworzyć maksymalny płaski wykres 2G z parzystymi wierzchołkami, po prostu zszywając dwie kopie G na zewnętrznej powierzchni. Jeśli G nie jest połączone 3, można trzykolorować jego 3 połączone elementy niezależnie.
David Eppstein
24

S.3)

Gil Kalai
źródło