Kolorowanie płaskich wykresów

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

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

Dzięki. Czy masz referencję na dowód?

— Lance Fortnow

Możesz spojrzeć na te dwa artykuły: google.com/… i google.com/…

— Joseph Malkevitch

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,

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