Graph union and chromatic number

Question

Let $G_p$ and $G_q$ be any two simple undirected graphs of $p$ and $q$ vertices, respectively. Does it hold that $G_q\subseteq G_p$ whenever $\chi(G_p\cup G_q)=$ $\chi(G_p)$?

The above statement holds true as so far as i tried. The union of two graphs $G_p$ and $G_q$ are defined as: $G_p\cup G_q=\langle V(G_p)\cup V(G_q), E(G_p)\cup E(G_q)\rangle$. The symbol '$\subseteq$' denotes the graph subset, and the symbol $\chi(G)$ denotes the chromatic number of the graph $ G$.

Answer 1

In general it does not. Let

• $G_2$ be a single edge. $G_2=K_2$ with $V(G_2)=\{1,2\}$ and $E(G_2)=\{(1,2)\}$
• $G_3$ be three isolated other vertices, $V(G_3)=\{3,4,5\}$ and $E(G_3)=\emptyset$

By your definition of union, $$V(G_2\cup G_3)=\{1,2,3,4,5\}\quad\text{ and }\quad E(G_2\cup G_3)=\{(1,2)\}$$ So that $$\chi(G_2\cup G_3)=\chi(G_2)=2$$

However $G_3\not\subseteq G_2$.

You need additional restriction.

Edit - Non trivial example Let

• $G_5=C_5$ the 5-cycle on vertex set $\{1,2,3,4,5\}$, so that $\chi(G_5)=3$
• $G_3=K_3$ the complete graph on vertex set $\{1,2,3\}$.

Note that $G_3\not\subseteq G_5$ but $\chi(G_5\cup G_3)=\chi(G_5)=3$$

Edit 2 Anticipating additional question, the results does not hold even if $V(G_p)\not\subseteq V(G_q)$ and $V(G_q)\not\subseteq V(G_p)$ and $V(G_p)\cap V(G_q)\neq\emptyset$ :

• $G_5=C_5$ the 5-cycle on vertex set $\{1,2,3,4,5\}$, so that $\chi(G_5)=3$
• $G_3=K_3$ the complete graph on vertex set $\{1,2,6\}$.

Again that $G_3\not\subseteq G_5$ but $\chi(G_5\cup G_3)=\chi(G_5)=3$$