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.

Proof:
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

Graphs and chromatic number are investigated. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.

Question on chromatic number of graph, adjacency matrix and list. ... Basics of chromatic number of graph, adjacency matrix and list are described. ...

Find the chromatic number of the graph given in part 2, and the number of colors needed to color the regions of the graph in part 3 (to ensure that adjacent ...

... It is easy to see that, for every n, the chromatic number of Gn is 3. To see that we would create a 4-critical graph by connecting vertex 0 to vertex 3n, note ...

... The numbers of vertices, edges, components, and Hamiltonian cycles ... vertex) that contains every vertex in the graph. ... e) λ(G) denotes the chromatic number of G ...

... Answer. Each digit can be filled with any of the 7 numbers, we have,. ...Chromatic Number. The chromatic number of a graph is the least number of colours it takes ...

Chromatic Numbers. ... 2. Let G = (V,E) be a graph where V {1,2,3,4,5,6,7,8,9 ... connecting to vertices a and b such that ab=0 (mod 3). What is the chromatic number of G ...

... By the definition of class one and two graphs and Vizing's Theorem, we know that G is of class one. So, the edge chromatic number of G is the maximum degree k ...