Объединение двух простых плоских графов имеет хроматическое число $\leq 12$

Question

Рассмотрим граф $G$являясь объединением двух простых плоских графов на одном и том же множестве вершин. Я хочу показать$\chi(G) \leq 12$.

Теорема четырех цветов указывает, что хроматическое число плоского графа меньше 4, а для общих графов $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Но это дало бы только верхнюю границу 16. Есть ли что-нибудь особенное в плоском графе, которое помогает уменьшить границу?

Answer 1

поскольку $G_1$ и $G_2$ плоские, у нас есть $|E(G_1)| \le 3|V(G_1)|-6$ и $|E(G_2)| \le 3|V(G_2)|-6$. поскольку$V(G_1) = V(G_2)$ учитывая, пусть $V = V(G_1) = V(G_2)$для удобства. Тогда у нас есть$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Теперь по лемме о рукопожатии мы также знаем, что $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Итак, легко увидеть, что существует вершина $v \in V$ такой, что $d_{G_1 \cup G_2}(v) < 12\ (*)$. Теперь воспользуемся индукцией по$|V|$.

Сейчас если $|V| = 1$, результат наглядный (на самом деле он понятен для $|V| \le 12$). Теперь предположим, что индуктивно это верно для плоских графов с$|V| = n$. Тогда для множества вершин с$|V| = n+1$, рассмотрим граф с множеством вершин $V-v$(Обратите внимание, что удаление вершины не может сделать планарный граф неплоским). Тогда по предположению индукции мы можем раскрасить этот граф не более чем в$12$цвета. Теперь добавьте$v$обратно со снятыми краями. От$(*)$, $d_{G_1 \cup G_2}(v) < 12$ поэтому мы можем раскрасить эту вершину по крайней мере в один из цветов, используемых в графе с набором вершин $V-v$ и мы закончили.

Answer 2

Планарные графы удовлетворяют $|E(G)| \le 3|V(G)|-6$, поэтому объединение двух плоских графов удовлетворяет $|E(G)| \le 6|V(G)|-12$, который мы можем использовать, чтобы показать, что существует вершина степени меньше, чем $12$.

Это приводит нас к доказательству по индукции: удалите эту вершину, раскрасьте остальные, а затем раскрасьте эту вершину. Индуктивная гипотеза применима, потому что любой подграф$G$является также объединение двух плоских графов: соответствующие подграфы$G_1$ и $G_2$.