1.2 Proper Vertex Colorings 3 number of graphs.If a graph G is the union or the join of k graphs G.G.....G for some integer k 2,then the chromatic number of G can be expressed in terms of the chromatic numbers of these k graphs. Theorem 1.2.2.Let G.G2.....Gg be k graphs wherek z2. ()fG=G+G2+…+Gs,hemX(G=max{x(G):1≤i≤k (lfG=GvGv…vG,hmx(G)=∑f=1xG) One of the most useful lower bounds for the chromatic number of a graph is stated next. Proposition 1.2.3.If H is a subgraph of a graph G.then x(H)(G) The clique number (G)of a graph G is the maximum order of a complete subgraph of G.The following result is therefore a consequence of Proposition 1.2.3. Corollary 1.2.4.For every graph G.(G)X(G). By Corollary 1.2.4 (or,in fact,by Observation 1.2.1(c)).if a aph G ontains a upper bounds for the chromatic number of a grap are concemed.th d (G)may diffe following result gives such a bound in terms of the maximum degree of the graph. Theorem 1..2.5.For every graph G,x(G)≤△(G+1. For each positive integer n,(Kn)=n =A(K)+1 and for each odd integer n≥3，X(Cn)=3=△(Ca)+l.The British mathematician Rowland Leonard Brooks showed that these wo of graphs are the graps with this property Theorem 1.2.6 ([11)).IfG is a connected graph that is neither an odd cycle nor a complete graph,then x(G)≤△(G). The distance d(u.v)between two vertices u and v in a connected graph G is the length of a shortest u-vpath and the diameter diam(G)of G is the greatest distance between two vertices of G.For a vertex v in a connected graph G,the eccentricin e(v)of v is the greatest distance between v and a vertex in G.Thus,the diameter of G is also the la eccentricit among all vertices of G.There is a for the chr pp order an liamete Theorem 1.2.7([291).If G is a connected graph of order n and diameter d,then X(G)≤n-d+1. 1.2 Proper Vertex Colorings 3 number of graphs. If a graph G is the union or the join of k graphs G1; G2;:::; Gk for some integer k  2, then the chromatic number of G can be expressed in terms of the chromatic numbers of these k graphs. Theorem 1.2.2. Let G1; G2;:::; Gk be k graphs where k  2. (i) If G D G1 C G2 CC Gk, then .G/ D maxf.Gi/ W 1  i  kg. (ii) If G D G1 _ G2 __ Gk, then .G/ D Pk iD1 .Gi/. One of the most useful lower bounds for the chromatic number of a graph is stated next. Proposition 1.2.3. If H is a subgraph of a graph G, then .H/  .G/. The clique number !.G/ of a graph G is the maximum order of a complete subgraph of G. The following result is therefore a consequence of Proposition 1.2.3. Corollary 1.2.4. For every graph G, !.G/  .G/. By Corollary 1.2.4 (or, in fact, by Observation 1.2.1(c)), if a graph G contains a triangle, then .G/  3. There are graphs G for which .G/ and !.G/ may differ significantly. As far as upper bounds for the chromatic number of a graph are concerned, the following result gives such a bound in terms of the maximum degree of the graph. Theorem 1.2.5. For every graph G, .G/  .G/ C 1. For each positive integer n, .Kn/ D n D .Kn/ C 1 and for each odd integer n  3, .Cn/ D 3 D .Cn/ C 1. The British mathematician Rowland Leonard Brooks showed that these two classes of graphs are the only connected graphs with this property. Theorem 1.2.6 ([11]). If G is a connected graph that is neither an odd cycle nor a complete graph, then .G/  .G/. The distance d.u; v/ between two vertices u and v in a connected graph G is the length of a shortest uv path and the diameter diam.G/ of G is the greatest distance between two vertices of G. For a vertex v in a connected graph G, the eccentricity e.v/ of v is the greatest distance between v and a vertex in G. Thus, the diameter of G is also the largest eccentricity among all vertices of G. There is an upper bound for the chromatic number of a connected graph in terms of the order and diameter of the graph, which is due to Vašek Chvátal. Theorem 1.2.7 ([29]). If G is a connected graph of order n and diameter d, then .G/  n d C 1: