Question

If we have two graph G = (V, E) and G0 = (V, E0 ) on the same set V of vertices we call the union G ∪ G0 the graph (V, E ∪ E0 ). Next we have two claim about the chromatic number χ(G ∪ G0 ) of G ∪ G0 .Prove that χ(G∪G0 ) ≤ χ(G)∗χ(G0 ). Hint: consider assigning a color to each vertex in V based on its color in colorings of G and G0 .

Answer 1

We use the colors on $G$ and $G_0$ to make pairs of colors and use these pairs as colors on $G\bigcup G_0$. Define coloring on $G$: $c_1(v)$ and on $G_0$ : $c_2(v)$ .

Then we get coloring on $G\bigcup G_0$ : $(c_1(v),c_(v))$ . So, we can get at most $\chi_1\chi_2$ different pairs of colors.