Explore BrainMass

Graphs : Chromatic Number

Show that the chromatic number of G_1 + G_2 isX(G_1) + X(G_2) for any two graphs G_1 and G_2.

Where X(G)is the Chromatic Number.
defn: X(G) a proper colouring or simply a colouring of the vertices of G is an assignment of colours to the vertices in such a way that adjacent vertices have distinct colours; X(G) is then the minimal number of colours in a (vertex) colouring of G. Thus, for example, X(C_(2k))=2 and X(C_(2k+1))=3

Chromatic number:

The chromatic number of a graph is the minimum number of colours required to colour it.

Solution Preview

Suppose X(G_1)=m, X(G_2) is n. Now we consider G=G_1+G_2. It means that first we do G_1 union G_2, after that, we make each vertex in G_1 adjacent with each vertex in G_2. In another word, if u is a vertex in G_1, v is a vertex in G_2, ...

Solution Summary
