Unión de gráficos y número cromático

Question

Dejemos que $G_p$ y $G_q$ sean dos grafos simples no dirigidos de $p$ y $q$ vértices, respectivamente. ¿Es cierto que $G_q\subseteq G_p$ siempre que $\chi(G_p\cup G_q)=$ $\chi(G_p)$ ?

La afirmación anterior es válida por lo que he probado. La unión de dos gráficos $G_p$ y $G_q$ se definen como: $G_p\cup G_q=\langle V(G_p)\cup V(G_q), E(G_p)\cup E(G_q)\rangle$ . El símbolo ' $\subseteq$ ' denota el subconjunto del gráfico, y el símbolo $\chi(G)$ denota el número cromático del gráfico $ G$ .

Answer 1

En general no lo hace. Dejemos que

• $G_2$ sea una sola arista. $G_2=K_2$ con $V(G_2)=\{1,2\}$ y $E(G_2)=\{(1,2)\}$
• $G_3$ sean otros tres vértices aislados, $V(G_3)=\{3,4,5\}$ y $E(G_3)=\emptyset$

Según su definición de unión, $$V(G_2\cup G_3)=\{1,2,3,4,5\}\quad\text{ and }\quad E(G_2\cup G_3)=\{(1,2)\}$$ De modo que $$\chi(G_2\cup G_3)=\chi(G_2)=2$$

Sin embargo, $G_3\not\subseteq G_2$ .

Necesita una restricción adicional.

Edición - Ejemplo no trivial Dejemos que

• $G_5=C_5$ el ciclo de 5 en el conjunto de vértices $\{1,2,3,4,5\}$ para que $\chi(G_5)=3$
• $G_3=K_3$ el gráfico completo en el conjunto de vértices $\{1,2,3\}$ .

Tenga en cuenta que $G_3\not\subseteq G_5$ pero $\chi(G_5\cup G_3)=\chi(G_5)=3$$

Edición 2 Anticipando una pregunta adicional, los resultados no se mantienen incluso si $V(G_p)\not\subseteq V(G_q)$ y $V(G_q)\not\subseteq V(G_p)$ y $V(G_p)\cap V(G_q)\neq\emptyset$ :

• $G_5=C_5$ el ciclo de 5 en el conjunto de vértices $\{1,2,3,4,5\}$ para que $\chi(G_5)=3$
• $G_3=K_3$ el gráfico completo en el conjunto de vértices $\{1,2,6\}$ .

De nuevo que $G_3\not\subseteq G_5$ pero $\chi(G_5\cup G_3)=\chi(G_5)=3$$