Der Vier-Farben-Satz (4CT) besagt, dass jeder planare Graph vierfarbig ist. Es gibt zwei Beweise von [Appel, Haken 1976] und [Robertson, Sanders, Seymour, Thomas 1997]. Beide Beweise sind computergestützt und ziemlich einschüchternd.
Es gibt verschiedene Vermutungen in der Graphentheorie, die 4CT implizieren. Die Lösung dieser Vermutungen erfordert wahrscheinlich ein besseres Verständnis der Beweise von 4CT. Hier ist eine solche Vermutung:
Vermutung : Sei ein ebener Graph, sei eine Menge von Farben und eine festkommafreie Involution. Sei so, dassC f : C → C L = ( L v : v ≤ V ( G ) )
- für alle und
- wenn dann für alle , für alle . f ( α ) ≤ L v v ≤ V α ≤ C
Dann gibt es einen des Graphen -coloring .G
Wenn Sie solche Vermutungen kennen, die 4CT implizieren, listen Sie sie bitte in jeder Antwort auf. Ich konnte keine umfassende Liste solcher Vermutungen finden.
quelle
Antworten:
4CT entspricht:
Ein algebraisches Äquivalent des Vierfarbensatzes wird vorgestellt. Das Äquivalent ist die Behauptung der Nichtzugehörigkeit einer Familie von Polynomen zu einer Familie von Polynomidealen über ein bestimmtes endliches Feld .[6]
quelle
Eine weitere mechanische Überprüfung des 4-Farben-Theorems wurde von George Gonthier bei Microsoft Research Cambridge durchgeführt. Der Unterschied zu seinem Beweis besteht darin, dass der gesamte Satz mit dem Coq-Beweisassistenten angegeben und mechanisch verifiziert wurde, während die anderen Beweise nur die in Assembler und C geschriebene Kernelberechnung enthalten und daher ein Fehlerrisiko darstellen. Gonthiers Beweis deckt sowohl die rechnerischen als auch die logischen Aspekte in nur 60.000 Zeilen Coq ab.
quelle
Ich habe in meinem Blog darüber gesprochen und unsere Erkenntnis ist: Zum Beispiel kann Taits Zustand geschwächt werden, da es eine Färbung gibt, die höchstens o (n) Fehler aufweist. Siehe hier: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/
quelle
Schauen Sie sich T. Saaty an, 13 farbenfrohe Variationen von Guthries 4-Farben-Vermutung American Math. Monthly, 79 (1972) 2-43 für viele Beispiele.
Auch in David Barnetts Buch Map Coloring, Polyhedra, und The Four-Colour Problem, MAA, Dolciani Series, Volume 8, 1983, sind viele Beispiele aufgeführt. Ein besonders interessantes Ergebnis in Barnetes Buch ist: Wenn es immer möglich ist, Eckpunkte eines konvexen Polyeders abzuschneiden, um ein 3-wertiges konvexes Polyeder zu erzeugen, so dass die Anzahl der Seiten jeder Fläche ein Vielfaches von drei ist, impliziert dies Wahrheit der Vier-Farben-Vermutung.
quelle
Die Hadwiger-Vermutung .
quelle
In der Arbeit Absolute Planar Retracts und Four Colour Conjecture hat Pavol Hell mehrere äquivalente Formulierungen für den 4CT bewiesen. Einer von ihnen lautet wie folgt:
(Ein Teilgraph eines Graphen ist ein Rückzug von wenn ein Homomorphismus so dass für alle . Absolut planar retract ist ein planares Diagramm, das ein Retract eines beliebigen planaren Diagramms ist, von dem es ein Subgraph ist.)G G r : V ( G ) → V ( H ) r ( v ) = v v ≤ V ( H )H G G r:V(G)→V(H) r(v)=v v∈V(H)
quelle
Jeder brückenlose kubische ebene Graph ist 3-Kanten-färbbar. (Dies entspricht aufgrund von Tait 4CT.)
quelle
Dror Bar-Natans Arbeit "Lie-Algebren und das Vier-Farben-Theorem" (Combinatorica 17-1 (1997) 43-52, letzte Aktualisierung Oktober 1999, arXiv: q-alg / 9606016 ) enthält eine ansprechende Aussage zu Lie-Algebren, die äquivalent ist das Vier-Farben-Theorem. Die in der Aussage vorkommenden Begriffe tauchen auch in der Theorie der endlichen Invarianten von Knoten (Vassiliev-Invarianten) und der 3-Mannigfaltigkeit auf.
quelle
Satz 2.4 in diesem Artikel http://www.sciencedirect.com/science/article/pii/0012365X9500109A# enthält eine andere Formulierung für den 4CT.
Bearbeiten: Für ein gegebenes Diagramm hat das Diagramm die Kanten von als Scheitelpunkte. zwei Kanten von sind in benachbart, wenn sie ein Dreieck in überspannen . Dann kann der 4CT wie folgt angegeben werden: Für jeden planaren Graphen die chromatische Zahl von der Cliquenzahl von .Δ ( G ) G G Δ ( G ) G G Δ ( G ) Δ ( G )G Δ(G) G G Δ(G) G G Δ(G) Δ(G)
Ich habe vergessen zu erwähnen, dass Albertson und Collins zuvor in der VeröffentlichungG K(G) G K(G) G
G K(G)
http://www.sciencedirect.com/science/article/pii/0095895684900352 die folgende ähnliche Tatsache bewiesen haben : Bei gegebenem Diagramm bezeichne das Diagramm, dessen Eckpunkte sind die Ränder der . Zwei Eckpunkte von sind benachbart, wenn die entsprechenden Kanten in in einer Clique enthalten sind. Dann ist die 4CT äquivalent zu: Für jeden planaren Graphen sind die chromatische Zahl und die Cliquenzahl von gleich.K ( G ) G K ( G ) G G K ( G )
quelle
Die allgemeine Beschreibung des automatisierten Beweises von Gonthier ist lesenswert, wenn Sie nach mehr Einsicht suchen.
Yuri Matiyasevich untersuchte mehrere probabilistische Anpassungen des Vier-Farben-Theorems, die positive Korrelationen zwischen zwei Ähnlichkeitsbegriffen zwischen Farbgebungen beinhalteten. Seine Beweise der Äquivalenz beruhen auf einem zugeordneten Graphpolynom, das einen weiteren wahrscheinlichen Hinweis auf Vermutungen liefert, die den Satz implizieren.
quelle
Ich habe gerade in einer Zeitung von Chalopin und Gonçalves (STOC '09) die folgende Vermutung von West gelesen:
Da parallele Segmente in einer solchen Darstellung eine unabhängige Menge bilden, impliziert diese Vermutung die 4CT, ist aber vielleicht noch stärker.
Die Referenz: West, Offene Probleme . SIAM J Discrete Math Newsletter, 2 (1): 10-12, 1991.
quelle
Ein Snark ist ein zusammenhängender, brückenloser kubischer Graph, der nicht mit drei Rändern färbbar ist. Nach Wikipedia lautet die Snark-Vermutung , die das 4CT verallgemeinert, wie folgt:
Wieder laut Wikipedia wurde ein Beweis für diese Vermutung im Jahr 2001 von Robertson, Sanders, Seymour und Thomas angekündigt.
quelle
"The Face Labeling Of Maximal Planar Graphs" ist der Titel meiner kürzlich veröffentlichten Arbeit, in der ich 4 Farben von Maximal Planar Graphs in Konsistenz der Gesichtsbeschriftung transformiert habe. Der Link zum Artikel lautet http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf
quelle
Wie
LH Kauffman, Neuformulierung des Kartenfarbensatzes , Discrete Mathematics 302 (2005) 145–172
weist darauf hin, dass das Primalitätsprinzip nach G. Spencer-Brown sowie die Eliahou-Kryuchkov-Vermutung äquivalente Umformulierungen des FCT sind.
quelle
Garry Bowlin und Matthew G. Brins Papier "Färben planarer Graphen über farbige Pfade in den Assoziedern", zuletzt überarbeitet am 12. Mai 2013, arXiv: 1301.3984 math.CO enthält die folgende Vermutung auf Seite 26:
Es wird behauptet, dass die Vermutung 6.4, die sich aus früheren Sätzen und Theoremen in der Arbeit ergibt, 4CT entspricht.
quelle
Ein k- Fluss in einem ungerichteten Graphen G ist ein gerichteter Graph, der durch Ersetzen jeder Kante in G durch einen Bogen und Zuweisen einer ganzen Zahl zwischen -k und k (exklusiv) abgeleitet wird, sodass für jeden Scheitelpunkt in G die Summe der ganzen Zahlen gilt Bögen zugewiesen, die auf diesen Scheitelpunkt zeigen, entspricht der Summe der Ganzzahlen, die Bögen zugewiesen sind, die auf diesen Scheitelpunkt zeigen. Ein NWZ (Nowhere Zero) k -Fluss ist ein k -Fluss, in dem keinem Lichtbogen die Nummer 0 zugewiesen wurde.
Für jeden planaren Graphen G ist das Dual von G der Graph, der einen Scheitelpunkt für jede Fläche in einer planaren Einbettung von G enthält , und zwei Scheitelpunkte in einem Dual teilen sich eine Kante, die sie für jede Kante verbindet, die die entsprechenden Flächen in G zwischen ihnen teilen in ihren Grenzen. Nach dem Flow-Colouring-Duality-Theorem von Tutte hat ein ebener Graph ohne Isthmus (dh eine Kante, deren Löschung die Anzahl der Komponenten erhöhen würde) einen NWZ- k- Flow, wenn sein Dual k- colourable ist. Mit anderen Worten, ein planares Diagramm ist nur dann 4-farbig, wenn sein Dual einen NWZ 4-Fluss aufweist.
Beachten Sie, dass 4CT für das betreffende ebene Diagramm keine Schleifen (Kanten, die einen Scheitelpunkt mit sich selbst verbinden) erfordert, da für jedes Diagramm mit einer Schleife keine Scheitelfarbe mit einer Reihe von Farben festgelegt werden kann, da ein Scheitelpunkt mit einer Schleife daher an a angrenzt Scheitelpunkt der gleichen Farbe, unabhängig von seiner Farbe.
quelle
Ich arbeite daran:
Wenn Sie den Satz für rechteckige Karten beweisen können, dh Karten, die aus überlappenden Blättern bestehen, haben Sie auch den 4ct bewiesen. Außerdem können bei der Suche nur Karten mit Flächen berücksichtigt werden, die mindestens 5 Kanten aufweisen.
Weitere Informationen finden Sie unter http://4coloring.wordpress.com/ .
quelle