Gründe für die eine grafische Darstellung kann nicht sein einfärbbar?

21

Während ein bisschen auf Argumentation dieser Frage habe ich versucht , all die verschiedenen Gründe für die eine grafische Darstellung zu identifizieren nicht sein kann einfärbbar. Dies sind die einzigen 2 Gründe, die ich bisher identifizieren konnte:kG=(VG,EG)k

  1. G enthält eine Clique der Größe . Dies ist der offensichtliche Grund.k+1
  2. Es existiert ein Subgraph von so dass beide folgenden Aussagen wahr sind:GH=(VH,EH)G

    • H ist nicht färbbar.k1
    • xVGVH yVH {x,y}EG . Mit anderen Worten existiert ein Knoten in aber nicht in , so dass mit jedem Knoten in .G H x HxGHxH

Wir können die beiden oben genannten Gründe als Regeln ansehen. Wenn Sie sie rekursiv anwenden, gibt es nur zwei Möglichkeiten, ein nicht färbbares Diagramm zu erstellen, das keine Clique enthält:k + 1kk+1

  1. Beginnen Sie mit einem Zyklus von gerader Länge (der färbbar ist) und wenden Sie dann Regel 2 für mal an. Beachten Sie, dass eine Kante nicht als Zyklus der Länge (andernfalls würde dieser Prozess die Bildung einer Clique bewirken ).k - 1 2 k + 12k12k+1
  2. Beginnen Sie mit einem Zyklus ungerader Länge (der färbbar ist) und wenden Sie dann Regel 2 für mal an. Die Länge des Startzyklus muss größer als (andernfalls würde dieser Prozess eine Clique bilden).3k23k+1

Frage

Gibt es einen anderen Grund als die obigen 2, der ein Diagramm nicht färbbar macht?k

 
Update 30/11/2012

Genauer gesagt, was ich brauche, ist ein Satz der Form:

Ein Graph hat genau dann eine chromatische Zahl wenn ...Gχ(G)=k+1

Hajós Kalkül , auf den Yuval Filmus in seiner Antwort hingewiesen hat, ist ein perfektes Beispiel für das, wonach ich suche, da ein Graph genau dann eine chromatische Zahl wenn er sich aus Axiom ableiten lässt. durch wiederholtes Anwenden der 2 Inferenzregeln des Kalküls. Die Hajószahl ist dann die minimale Anzahl von Schritten, die erforderlich sind, um abzuleiten (dh es ist die Länge des kürzesten Beweises).Gχ(G)=k+1Kk+1h(G)G

Es ist sehr interessant, dass:

  • Die Frage, ob es einen Graphen dessen in der Größe von exponentiell ist, ist noch offen.Gh(G)G
  • Wenn eine solche nicht vorhanden, dann N P = c o N P .GNP=coNP
Giorgio Camerani
quelle
5
Ich wiederhole meinen Kommentar zu der Frage, auf die Sie verweisen, falls Ihnen der Satz von Erdős nicht bekannt ist (jeder, der über das Färben nachdenkt, sollte das so sein): Wenn die natürlichen Zahlen g und k gegeben sind, gibt es einen Graphen mit einem Umfang von mindestens g und chromatisch Anzahl mindestens k. Der Umfang eines Diagramms entspricht der Größe des kleinsten Zyklus. Wenn Sie also einen Umfang von mindestens 3 haben, hat jede maximale Clique die Größe 2 (jede Kante ist eine maximale Clique).
Pål GD
2
Eine einfache Beobachtung, die oft hilfreich ist: Jede Farbklasse ist eine eigenständige Menge. Wenn Sie nachweisen können, dass es keinen großen unabhängigen Satz gibt, dann wissen Sie, dass Sie viele Farben benötigen.
Jukka Suomela
1
Wenn es immer einen einfachen Grund dafür gäbe, dass Diagramme nicht farbig sind, wäre das Problem der Diagrammfärbung nicht NP-hart. Es sei denn P = NP, sind einige Diagramme nicht k -colorable nur weil . kk
Jeffs
5
@ Jɛ ɛ E: Ein Grund mag einfach, aber schwer zu berechnen sein. Es gibt einen ziemlich einfachen Grund, warum ein Graph eine Clique hat oder nicht , aber es ist immer noch NP-schwer. k
Luke Mathieson

Antworten:

29

Sie sollten den Hajós-Kalkül überprüfen . Hajós zeigte, dass jeder Graph mit einer chromatischen Zahl von mindestens einen Untergraphen hat, der einen "Grund" für die Anforderung von k Farben hat. Der fragliche Grund ist ein Proofsystem für die Anforderung von k Farben. Das einzige Axiom ist K k , und es gibt zwei Schlußregeln. Siehe auch dieses Papier von Pitassi und Urquhart über die Effizienz dieses Beweissystems.kkkKk

Yuval Filmus
quelle
1
Ausgezeichnet, das ist, wonach ich gesucht habe.
Giorgio Camerani
1
Danke für den Hinweis. Ich wusste vorher nichts über den Bau von Hajos.
Chandra Chekuri
15

Eine teilweise Antwort, in der ich keinen guten "Grund" kenne, der verallgemeinert werden kann, sondern die folgende Grafik (von hier aus schamlos geklaut ):

Nicht 3-farbiges Diagramm ohne K4 oder ungeraden Zyklus mit einem vollständig verbundenen Nachbarn

Ist nicht 3-färbbar, aber offensichtlich 4-färbbar (planar) und enthält weder noch einen Zyklus mit einem zusätzlichen Scheitelpunkt, der mit allen Zyklusscheitelpunkten verbunden ist (es sei denn, mir fehlt etwas, aber die einzigen Scheitelpunkte) verbunden mit einem Eckpunkt und seinem Nachbarn sind in den 3-Zyklen). Wenn Sie weiter gehen, können Sie eine Version von Regel 2 anwenden, um ein Diagramm der chromatischen Zahl 5 zu erhalten.K4

Ich würde vermuten, dass es für eine bestimmte Gattung eine Grafik mit einer bestimmten chromatischen Mindestzahl gibt (siehe die Heawood-Vermutung ), die nicht den Regeln 1 oder 2 entspricht. Natürlich habe ich keinen anderen Beweis als die Intuition.

Luke Mathieson
quelle
Der Petersen-Graph ist ein kleineres Beispiel für dasselbe. Sowohl die oben und der Petersen Graph hat die Kinder und Jugendliche , obwohl, das aus dem obigen Kommentar über Hadwiger-geht. K4
William Macrae
1
Die Hadwiger - Vermutung ist zwar eine notwendige Bedingung, aber nicht ausreichend, so dass eine grafische Darstellung , die chromatische Zahl hat genau dann , wenn es einen hat K k kleinere und etwas anderes . Wie JEFFE natürlich weist darauf hin, es ist wahrscheinlich , dass das etwas anderes ist , nur weil (in dem Sinne , dass es keine einfache Antwort ist). kKk
Luke Mathieson
@ LukeMathieson: Sehr interessant. Haben Sie ein Beispiel eines Graphen , der eine hat - Moll und das ist k - 1 einfärbbar? Kkk1
Giorgio Camerani
5
Nehmen Sie ein und unterteilen Sie alle Kanten. Die resultierende Grafik ist zweiteilig und somit zweifarbig, hat aber offensichtlich die vollständige Grafik als Nebenfigur. Kk
Luke Mathieson
12

Lovasz fand topologische Hindernisse für die k-Färbbarkeit und verwendete seine Theorie, um Knasers Vermutung zu lösen. Sein Satz ist der folgende. Sei G ein zusammenhängender Graph und sei N (G) ein simplizialer Komplex, dessen Flächen Teilmengen von V sind, die gemeinsame Nachbarn haben. Wenn dann N (K) k-verbunden ist (dh alle seine reduzierten Homologiegruppen sind 0 bis zur Dimension k-1), dann beträgt die Anzahl der Farben, die zum Färben von G benötigt werden, mindestens k + 3.

Gil Kalai
quelle
11

Es kann genauso wichtig sein, keine große unabhängige Gruppe zu haben wie eine große Clique.

Ein wichtiges Hindernis dafür, dass ein Graph nicht k-färbbar ist, besteht darin, dass die maximale Größe einer unabhängigen Menge kleiner als n / k ist, wobei n die Anzahl der Eckpunkte ist. Dies ist ein sehr wichtiges Hindernis. Zum Beispiel impliziert dies, dass ein Zufallsgraph in G (n, 1/2) eine chromatische Zahl von mindestens n / log n hat.

Ein genaueres Hindernis ist, dass es für jede Zuweisung von nichtnegativen Gewichten für die Eckpunkte keine unabhängige Menge gibt, die einen Bruchteil von 1/5 (oder mehr) des Gesamtgewichts erfasst. Beachten Sie, dass dies auch die "Keine-Clique-Hindernisse" einschließt. Die LP-Dualität sagt Ihnen, dass dieses Hindernis äquivalent zu der "gebrochenen chromatischen Zahl" von G ist, die größer als k ist.

Es gibt auch Hindernisse für die k-Färbbarkeit anderer Art, die manchmal über die fraktionierte chromatische Zahlensperre hinausgehen. Ich werde ihnen eine separate Antwort geben.

Gil Kalai
quelle
Danke für deine Antwort! Das raffiniertere Hindernis, das Gewichte und unabhängige Sätze bindet, ist äußerst interessant ...
Giorgio Camerani
11

Umformulieren Sie die Frage wie folgt: "Genauer gesagt, ich brauche einen Satz der Form: Ein Graph hat die chromatische Zahl χ ( G ) = k + 1 genau dann, wenn ...":Gχ(G)=k+1

Gχ(G)kGk1

David Eppstein
quelle
Vielen Dank! Dies ist definitiv 100% ausreichend. Es passt perfekt zur Neuformulierung der Frage.
Giorgio Camerani