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 .
The Answer to the Question
is below this banner.
Here's the Solution to this Question
We use the colors on and to make pairs of colors and use these pairs as colors on . Define coloring on : and on : .
Then we get coloring on : . So, we can get at most different pairs of colors.