Solution to If we have two graph G = (V, E) and G0 = (V, E0 ) … - Sikademy
Author Image

Archangel Macsika

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.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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 Gc_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.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3415-qpid-2114