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

Chromatic Numbers and Graph Coloring. ... (The minimum integer for which a graph is k-colorable is called the vertex chromatic number, or simply the chromatic...

Vertex Chromatic Numbers and Betti Numbers. ... X(G) is the minimum integer k for which a graph G is k-colorable is called the vertex chromatic number. ...

... We know that the vertices 1,3,6,9,12 form a clique with size 5. So, we know that the chromatic number is at least 5. We can color the graph G in 5 colors as ...

...Chromatic Numbers. Show that K3,3 has list-chromatic number 3. Please can you explain what does list-chromatic number means and don't forget to draw a graph. ...

... Proof : Let G we any graph of 2 face colourable. Then dual graph of G., ie G* having chromatic number ψ (G)= 2. Therefore G* is a bipartite graph. ...

... By Vizing's Theorem for the edge chromatic number χ ' (G ) , we know that ∆ (G ) ≤ χ ... 1) where ∆ (G ) is the maximum degree of a simple graph G. Since ...

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