İki basit düzlemsel grafiğin birleşimi kromatik numaraya sahiptir $\leq 12$
Grafiği düşünün $G$iki basit düzlemsel grafiğin aynı köşe kümesinde birleşimidir. göstermek istiyorum$\chi(G) \leq 12$.
Dört renk teoremi, düzlemsel bir grafiğin kromatik sayısının 4'ten az olduğunu ve genel grafikler için $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Ancak bu yalnızca 16'nın üst sınırını verir. Sınırı azaltmaya yardımcı olan düzlemsel grafiğe özgü herhangi bir şey var mı?
Yanıtlar
Dan beri $G_1$ ve $G_2$ düzlemsel, bizde $|E(G_1)| \le 3|V(G_1)|-6$ ve $|E(G_2)| \le 3|V(G_2)|-6$. Dan beri$V(G_1) = V(G_2)$ verilen $V = V(G_1) = V(G_2)$kolaylık sağlamak için. O zaman bizde$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Şimdi, Handshaking Lemma ile bunu da biliyoruz $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Böylece, bir tepe noktası olduğu kolayca görülebilir. $v \in V$ öyle ki $d_{G_1 \cup G_2}(v) < 12\ (*)$. Şimdi, tümevarımı kullanacağız$|V|$.
Şimdi eğer $|V| = 1$sonuç açıktır (aslında nettir $|V| \le 12$). Şimdi, tümevarımlı olarak düzlemsel grafikler için geçerli olduğunu varsayalım.$|V| = n$. Ardından, bir tepe noktası için$|V| = n+1$, köşe ayarlı bir grafik düşünün $V-v$(Bir tepe noktasını kaldırmanın bir düzlemsel grafiği düzlemsel olmayan yapamayacağını unutmayın). Ardından, tümevarım hipotezi ile bu grafiği en fazla$12$renkler. Şimdi ekle$v$kaldırılmış kenarlarla geri dönün. Tarafından$(*)$, $d_{G_1 \cup G_2}(v) < 12$ Böylece bu tepe noktasını, köşe kümesi ile grafikte kullanılan renklerden en az biriyle renklendirebiliriz $V-v$ ve bitirdik.
Düzlemsel grafikler tatmin eder $|E(G)| \le 3|V(G)|-6$, böylece iki düzlemsel grafiğin birleşimi, $|E(G)| \le 6|V(G)|-12$, bundan daha düşük bir derecenin tepe noktası olduğunu göstermek için kullanabiliriz $12$.
Bu bizi tümevarım yoluyla bir ispata götürür: o tepe noktasını kaldırın, geri kalanını renklendirin ve sonra bu tepe noktasını renklendirin. Endüktif hipotez geçerlidir çünkü herhangi bir alt grafik$G$aynı zamanda iki düzlemsel grafiğin birleşimidir: karşılık gelen alt grafikleri$G_1$ ve $G_2$.