La unión de dos gráficos planos simples tiene un número cromático $\leq 12$

Question

Considere el gráfico $G$siendo la unión de dos grafos planos simples ambos en el mismo conjunto de vértices. quiero mostrar$\chi(G) \leq 12$.

El teorema de los cuatro colores indica que el número cromático de un gráfico plano es menor que 4, y para gráficos generales $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$. Pero esto solo produciría un límite superior de 16. ¿Hay algo en particular en el gráfico plano que ayude a reducir el límite?

Answer 1

Ya que $G_1$ y $G_2$ son planas, tenemos $|E(G_1)| \le 3|V(G_1)|-6$ y $|E(G_2)| \le 3|V(G_2)|-6$. Ya que$V(G_1) = V(G_2)$ dado, deja $V = V(G_1) = V(G_2)$por conveniencia. Entonces tenemos$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ Ahora, por Handshaking Lemma, también sabemos que $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ Entonces, uno puede ver fácilmente que existe un vértice $v \in V$ tal que $d_{G_1 \cup G_2}(v) < 12\ (*)$. Ahora, usaremos la inducción en$|V|$.

Ahora si $|V| = 1$, el resultado es claro (en realidad lo es para $|V| \le 12$). Ahora, suponga que inductivamente se cumple para gráficos planos con$|V| = n$. Luego, para un vértice configurado con$|V| = n+1$, considere un gráfico con vértice establecido $V-v$(Tenga en cuenta que eliminar un vértice no puede hacer que un gráfico plano no sea plano). Luego, por hipótesis de inducción, podemos colorear este gráfico con como máximo$12$colores. Ahora agregue$v$espalda con los bordes eliminados. Por$(*)$, $d_{G_1 \cup G_2}(v) < 12$ para que podamos colorear este vértice con al menos uno de los colores utilizados en el gráfico con el conjunto de vértices $V-v$ y hemos terminado.

Answer 2

Los gráficos planos satisfacen $|E(G)| \le 3|V(G)|-6$, por lo que la unión de dos gráficas planas satisface $|E(G)| \le 6|V(G)|-12$, que podemos usar para mostrar que hay un vértice de grado menor que $12$.

Esto nos lleva a una prueba por inducción: quita ese vértice, colorea el resto y luego colorea ese vértice. La hiptesis inductiva se aplica porque cualquier subgrafo de$G$es también una unión de dos grafos planos: los subgrafos correspondientes de$G_1$ y $G_2$.