A união de dois grafo planar simples tem número cromático $\leq 12$

Question

Considere o gráfico $G$sendo a união de dois grafos planares simples, ambos no mesmo conjunto de vértices. eu quero mostrar$\chi(G) \leq 12$.

Teorema de quatro cores indica que o número cromático de um gráfico plano é menor que 4, e para gráficos gerais $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Mas isso resultaria apenas em um limite superior de 16. Existe algo em particular no gráfico planar que ajude a reduzir o limite?

Answer 1

Desde a $G_1$ e $G_2$ são planas, nós temos $|E(G_1)| \le 3|V(G_1)|-6$ e $|E(G_2)| \le 3|V(G_2)|-6$. Desde a$V(G_1) = V(G_2)$ dado, vamos $V = V(G_1) = V(G_2)$Por conveniência. Então nós temos$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Agora, por Handshaking Lemma, também sabemos que $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Então, pode-se facilmente ver que existe um vértice $v \in V$ de tal modo que $d_{G_1 \cup G_2}(v) < 12\ (*)$. Agora, vamos usar a indução em$|V|$.

Agora se $|V| = 1$, o resultado é claro (na verdade, é claro para $|V| \le 12$) Agora, suponha que indutivamente é válido para gráficos planares com$|V| = n$. Então, para um conjunto de vértices com$|V| = n+1$, considere um gráfico com conjunto de vértices $V-v$(Observe que remover um vértice não pode tornar um grafo plano não plano). Então, por hipótese de indução, podemos colorir este gráfico com no máximo$12$cores. Agora adicione$v$de volta com as bordas removidas. De$(*)$, $d_{G_1 \cup G_2}(v) < 12$ então podemos colorir este vértice com pelo menos uma das cores usadas no gráfico com conjunto de vértices $V-v$ e nós terminamos.

Answer 2

Os gráficos planos satisfazem $|E(G)| \le 3|V(G)|-6$, então a união de dois gráficos planares satisfaz $|E(G)| \le 6|V(G)|-12$, que podemos usar para mostrar que há um vértice de grau menor que $12$.

Isso nos leva a uma prova por indução: remova esse vértice, pinte o resto e depois pinte esse vértice. A hipótese indutiva se aplica porque qualquer subgráfico de$G$é também uma união de dois gráficos planares: os subgráficos correspondentes de$G_1$ e $G_2$.