Gabungan dua graf planar sederhana memiliki bilangan kromatik $\leq 12$

Question

Pertimbangkan grafik $G$menjadi gabungan dari dua grafik planar sederhana pada kumpulan simpul yang sama. Saya ingin menunjukkan$\chi(G) \leq 12$.

Teorema empat warna menunjukkan bahwa bilangan kromatik grafik planar kurang dari 4, dan untuk grafik umum $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Tapi ini hanya akan menghasilkan batas atas 16. Apakah ada sesuatu yang khusus pada grafik planar yang membantu mengurangi batas?

Answer 1

Sejak $G_1$ dan $G_2$ adalah planar, kami punya $|E(G_1)| \le 3|V(G_1)|-6$ dan $|E(G_2)| \le 3|V(G_2)|-6$. Sejak$V(G_1) = V(G_2)$ diberikan, biarkan $V = V(G_1) = V(G_2)$untuk kenyamanan. Lalu kita punya$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Nah, dengan Handshaking Lemma, kita juga tahu itu $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Jadi, orang dapat dengan mudah melihat bahwa ada sebuah simpul $v \in V$ seperti yang $d_{G_1 \cup G_2}(v) < 12\ (*)$. Sekarang, kita akan menggunakan induksi$|V|$.

Sekarang, jika $|V| = 1$, hasilnya jelas (sebenarnya sudah jelas $|V| \le 12$). Sekarang, anggaplah secara induktif itu berlaku untuk grafik planar dengan$|V| = n$. Kemudian, untuk set simpul dengan$|V| = n+1$, pertimbangkan grafik dengan kumpulan titik $V-v$(Perhatikan bahwa menghapus simpul tidak dapat membuat graf planar menjadi non-planar). Kemudian, dengan hipotesis induksi, kita dapat mewarnai grafik ini paling banyak$12$warna. Sekarang tambahkan$v$kembali dengan ujung yang dilepas. Oleh$(*)$, $d_{G_1 \cup G_2}(v) < 12$ jadi kita bisa mewarnai simpul ini dengan setidaknya satu dari warna yang digunakan dalam graf dengan set simpul $V-v$ dan kita selesai.

Answer 2

Grafik planar memuaskan $|E(G)| \le 3|V(G)|-6$, sehingga penyatuan dua grafik planar memuaskan $|E(G)| \le 6|V(G)|-12$, yang bisa kita gunakan untuk menunjukkan bahwa ada simpul berderajat kurang dari $12$.

Ini membawa kita ke pembuktian dengan induksi: singkirkan simpul itu, warnai sisanya, lalu warnai simpul itu. Hipotesis induktif berlaku karena setiap subgraf$G$adalah juga sebuah serikat dua grafik planar: yang subgraf yang sesuai$G_1$ dan $G_2$.