Färben von ebenen Diagrammen

21

Betrachten Sie die Menge der ebenen Graphen, bei denen alle inneren Flächen Dreiecke sind. Wenn es einen Innenpunkt ungeraden Grades gibt, kann das Diagramm nicht dreifarbig sein. Wenn jeder Innenpunkt einen gleichmäßigen Grad hat, kann er immer dreifarbig sein? Idealerweise hätte ich gerne ein kleines Gegenbeispiel.

graph-theory co.combinatorics graph-colouring Lance Fortnow
quelle

Antworten:

25

Ja, dies ist eine Folge des Drei-Farben-Satzes, siehe unten: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
quelle
1
Vielen Dank. Haben Sie eine Referenz für einen Beweis?
Lance Fortnow
3
Sie könnten sich diese beiden
Artikel
6
Um Malkevitchs Referenzen zu ergänzen: Die Äquivalenz von 3-Färbbarkeit und sogar Grad für planare Triangulationen wird gewöhnlich PJ Heawood zugeschrieben, "On the four-colour map theorem". Vierteljährlich J. Pure Appl. Mathematik. 29: 270–285, 1898. Die von Malkevitch verlinkten Zeitungen haben jedoch mehr zu dieser Zuschreibung zu sagen.
David Eppstein
6
Auch die Konsequenz wird in Hulls Notizen nicht erwähnt, sondern nur der 3-Farben-Satz selbst. Aus einem 3-zusammenhängenden Graphen G mit dreieckigen Innenflächen und sogar Innenscheitelpunkten kann man jedoch einen maximal planaren Graphen 2G mit geraden Scheitelpunkten bilden, indem man einfach zwei Kopien von G auf die Außenfläche stickt. Wenn G nicht 3-fach verbunden ist, kann man seine 3-fach verbundenen Komponenten unabhängig voneinander 3-fach färben.
David Eppstein
24

S3

Gil Kalai
quelle