Si $G$ y $H$ son $k$ -crítico, entonces aplicando la construcción de Hajós a $G$ y $H$ hace $k$ -Gráfico crítico

Question

Esta es la definición de la construcción de Hajós.

Dejemos que $G$ y $H$ sean dos grafos no dirigidos, $vw$ sea una arista de $G$ y $xy$ sea una arista de $H$ .
Entonces la construcción de Hajós forma un nuevo grafo que combina los dos grafos identificando los vértices $v$ y $x$ en un solo vértice, eliminando las dos aristas $vw$ y $xy$ y añadiendo un nuevo borde $wy$ .

En muchos artículos sobre la construcción de Hajós, consideran la siguiente afirmación como un "hecho":

Si $G$ y $H$ son $k$ -crítico, entonces aplicando la construcción de Hajós a $G$ y $H$ obtiene un $k$ -Gráfico crítico.

Pero no tengo ni idea de cómo probarlo.
¿Me ayudarías?

Answer 1

Dejemos que $G$ y $H$ sea $k$ -Gráficos críticos y $G +_h H$ sea la construcción de Hajós aplicada a $G$ y $H$ con respecto a $vw \in E(G)$ y $xy \in E(H)$ . Desde $G$ y $H$ son $k$ -Crítico, $G-vw$ y $H-xy$ ambos tienen $(k-1)$ -colores. Permutar los colores para que el color de $v$ es el mismo que el color de $x$ . Luego, recolocar el color $w$ con el nuevo color $k$ . Esto da lugar a un $k$ -coloración de $G +_h H$ . Para llegar a una contradicción, supongamos $c$ es un $(k-1)$ -coloración de $G +_h H$ . Desde $\chi(G)=k$ Debemos tener $c(v)=c(w)$ . Del mismo modo, ya que $\chi(H)=k$ , $c(x)=c(y)$ . Esto implica $c(w)=c(y)$ , lo que contradice que $c$ es una coloración adecuada. Así, $\chi(G +_h H)=k$ .

Queda por demostrar que para cada arista $e$ de $G +_h H$ , eliminando $e$ disminuye el número cromático de $G +_h H$ . Si $e=wy$ entonces el argumento anterior (sin el paso de recolocación) muestra que $\chi( (G +_h H) \setminus e) \leq k-1$ . Por lo tanto, por simetría, podemos suponer que $e \in E(G)$ . Desde $G$ est $k$ -Crítico, $G \setminus e$ tiene un $(k-1)$ -colorear $c$ . Desde $H$ est $k$ -Crítico, $H \setminus xy$ tiene un $(k-1)$ -colorear $c'$ . Desde $\chi(H)=k$ , $c'(x)=c'(y)$ . Desde $vw \in E(G \setminus e)$ , $c(v) \neq c(w)$ . Por lo tanto, permutando los colores para que $c(v)=c'(x)$ da una $(k-1)$ -coloración de $(G +_h H) \setminus e$ .