Die Vereinigung zweier einfacher planarer Graphen hat eine chromatische Zahl $\leq 12$

Dec 16 2020

Betrachten Sie die Grafik $G$Dies ist die Vereinigung zweier einfacher planarer Graphen, die sich beide auf demselben Satz von Eckpunkten befinden. Ich will zeigen$\chi(G) \leq 12$.

Der Vierfarbensatz zeigt an, dass die chromatische Zahl eines planaren Graphen kleiner als 4 ist, und für allgemeine Graphen $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Dies würde jedoch nur eine Obergrenze von 16 ergeben. Gibt es etwas Besonderes an einem planaren Graphen, das dazu beiträgt, die Grenze zu verringern?

Antworten

1 ArsenBerk Dec 15 2020 at 23:50

Schon seit $G_1$ und $G_2$ sind planar, wir haben $|E(G_1)| \le 3|V(G_1)|-6$ und $|E(G_2)| \le 3|V(G_2)|-6$. Schon seit$V(G_1) = V(G_2)$ gegeben, lassen $V = V(G_1) = V(G_2)$zur Bequemlichkeit. Dann haben wir$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Nun, durch Handshaking Lemma wissen wir das auch $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Man kann also leicht erkennen, dass es einen Scheitelpunkt gibt $v \in V$ so dass $d_{G_1 \cup G_2}(v) < 12\ (*)$. Jetzt werden wir die Induktion aktivieren$|V|$.

Nun, wenn $|V| = 1$ist das Ergebnis klar (eigentlich ist es klar für $|V| \le 12$). Nehmen wir nun an, es gilt induktiv für planare Graphen mit$|V| = n$. Dann für einen Scheitelpunkt mit$|V| = n+1$Betrachten Sie ein Diagramm mit Scheitelpunktsatz $V-v$(Beachten Sie, dass das Entfernen eines Scheitelpunkts ein planares Diagramm nicht nicht planar machen kann.) Dann können wir durch Induktionshypothese diesen Graphen höchstens mit färben$12$Farben. Fügen Sie nun hinzu$v$zurück mit den entfernten Kanten. Durch$(*)$, $d_{G_1 \cup G_2}(v) < 12$ Daher können wir diesen Scheitelpunkt mit mindestens einer der im Diagramm verwendeten Farben färben, wobei der Scheitelpunkt festgelegt ist $V-v$ und wir sind fertig.

2 MishaLavrov Dec 15 2020 at 23:42

Planare Graphen erfüllen $|E(G)| \le 3|V(G)|-6$, also erfüllt die Vereinigung zweier planarer Graphen $|E(G)| \le 6|V(G)|-12$, mit dem wir zeigen können, dass es einen Gradscheitelpunkt von weniger als gibt $12$.

Dies führt uns zu einem Beweis durch Induktion: Entfernen Sie diesen Scheitelpunkt, färben Sie den Rest und färben Sie dann diesen Scheitelpunkt. Die induktive Hypothese gilt, weil jeder Untergraph von$G$ist auch eine Vereinigung von zwei planaren Graphen: die entsprechenden Untergraphen von$G_1$ und $G_2$.