Cromática número en una unión de grafos planares

Question

Estoy tratando de resolver el siguiente problema:

Deje $G_1, G_2, \dots,G_{100}$ $100$ grafos planares en el mismo conjunto de vértices $V$ , con el borde conjuntos de $E_1, E_2,...,E_{100}$, respectivamente, y considere la gráfica de $G = (V, \bigcup_{i=1}^{100}E_i)$ que es la unión de los gráficos $G_1, G_2,\dots,G_{100}$. Demostrar que $\chi(G) ≤ 600$.

Traté de jugar con la desigualdad de $E(G) \leq 3 |G| - 6$ que se cumple para cualquier plano gráfico, y también con el hecho de que podemos hacer cualquier color plano gráfico con 4 colores, pero no he podido avanzar después de eso. Yo también, aunque de inducción sobre el número de vértices de manera que yo pudiera hacer eso para un conjunto arbitrario de los vértices, pero esto no me ayuda.

¿Alguien puede proporcionar una pista o dirección para que yo pueda hacer algún progreso?

Answer 1

La desigualdad de $|E(G)| \le 3 |V(G)| - 6$ es más útil la dirección para ir de aquí que el $4$-color teorema. La prueba de este resultado es más similar a la prueba de la $6$-color teorema que, en resumen, va como sigue:

• De la desigualdad anterior, se deduce que el grado medio de cualquier plano gráfico es estrictamente menor que $6$, por lo que debe haber un vértice de $v$ grado menos de $6$:$5$.
• Procedemos por inducción sobre el número de vértices. Por la hipótesis inductiva, se puede colorear $G-v$ $6$ colores.
• Podemos extender el colorante de $G-v$ a un colorante de $G$ coloreando $v$ un color diferente de los colores utilizados en sus vecinos (hay en la mayoría de las $5$ vecinos, $6$ colores, por lo que un color no se utiliza).

Este argumento se generaliza a un argumento basado en la degeneración de un gráfico. Un $k$degenerada subgrafo es uno en el que cada subgrafo tiene un vértice de grado en la mayoría de las $k$. La desigualdad anterior muestra que un grafo es planar $5$degenerada, y una similar inductivo argumento muestra que todos los $k$degenerada gráficos se $(k+1)$-engañosa.

Así que si usted demostrar que la unión de $100$ grafos planares es $599$-degenerado, usted tendrá una prueba de que el es $600$-engañosa.

Answer 2

Creo que tengo la respuesta. el $G_1, ..., G_{100}$ son grafos planares en el mismo conjunto de vértices, lo que |V| es el mismo para todos los $G_i$.

Sabemos $|E(G_i)|≤3|V|−$6 $\forall i $, ya que todos ellos son planas por lo tanto $ |\bigcup_{i=1}^{100}E_i| \leq |\sum_{i=1}^{100} E_i| ≤100 (3|V|-6)= 300|V|-600$

Por comodidad vamos a $ E = \bigcup_{i=1}^{100}E_i$

Por el grado de la fórmula de la suma o apretón de manos lema,$\sum_{v} deg(v) = 2|E| \leq 2*(300|V|-600) = 600 |V|-1200 $, por lo tanto existe una prueba por contradicción o grado medio) de un vértice $v$ con grado estrictamente menor que 600, es decir, de grado menor o igual a 599. Por lo tanto, ya que cada subgrafo de la unión de 100 grafos planares tiene un vértice de grado menor o igual a 599, la gráfica es, por definición, 599 - degenerado y por lo tanto de 600 colourable.

Es esto correcto?