¿Podemos determinar el número cromático de la unión de dos grafos

Question

Pregunta:

Sea $G_1=(V_1,E_1)$ sea un grafo cuando su número cromático sea 7, y sea $G_2=(V_2,E_2)$ cuando su número cromático es 5. Además, $|V_1\cap V_2|=2$ . Sea $G_3=(V_3,E_3)$ tal que $V_3=V_1\cup V_2$ . ¿Podemos determinar cuál es el número cromático de $G_3$ ?

---

$Solution.$

Para esta pregunta podemos fijarnos en los gráficos $K_5$ y $K_7$ porque satisfacen los números cromáticos requeridos.

Sabemos que el gráfico $G_3$ es la unión de ambos grafos, de forma que tenemos dos vértices en común, por lo que hay que poner $K_5$ en un borde de $K_7$ .

Por ejemplo, tenemos:

y después de la unión obtenemos:

por lo que obtenemos que el número cromático de $G_3$ es 7.

---

Ahora bien, ¿es correcto? porque no estoy seguro de que esto sea correcto siempre. Estaré encantado de recibir una explicación. Gracias.

Answer 1

Toma un $K_9$ gráfico completo. Etiqueta tres vértices como $\{v_1, v_2, v_3\}$ y borrar el triángulo de bordes entre ellos. Se obtiene un grafo con número cromático $7$ . Sea $V_1 \cap V_2 = \{v_1, v_2\}$ . Observe que $v_1, v_2$ tienen que tener el mismo color en todas las coloraciones del gráfico con siete colores. Observa que si dos vértices cualesquiera entre $\{v_1, v_2, v_3\}$ tuviéramos un nuevo borde, tendríamos un $K_8$ subgrafo dentro de él, por lo que el color cromático aumentaría.

Ahora toma $K_5$ como el grafo con número cromático $5$ . La unión de estos dos grafos tiene una arista entre $v_1, v_2$ . Así que, como se ha dicho antes, tenemos un $K_8$ subgrafo dentro de la unión, por lo que el color cromático debe ser al menos $8$ .

La idea detrás de este contraejemplo es: Que el grafo con más colores tenga los mismos colores en la intersección, y que el otro grafo añada aristas en esa intersección. Estas nuevas aristas fuerzan colores adicionales. Espero que esto aclare un poco lo que decía en los comentarios.