4 I Introduction G has a k-vertex coloring is called the chromatic number of G.denoted by x(G). For graphs of order n>3,it is immediate which graphs of order n have chromatic number 1.n or 2. Observation 1.9.If G is a graph of order n3.then (a)y(G)=1 if and only if G is empty (b)x(G)=n if and only ifG=K (c)X(G)=2if and only if G is a nonempty bipartite graph An immediate consequence of Observation 1.9(c)is that x(G)3 if and only if G contains an odd cycle.One of the most useful lower bounds for the chromatic number of a graph is stated below. Proposition 1.10.If H is a subgraph of a graph G.then x(H)<x(G). The clique number (G)of a graph G is the maximum order of a complete subgraph of G.The following result is herefore a consequence of Proposition1.10 Corollary 1.11.For every graph G,(G)X(G) By Corollary 1.11 (or,in fact,by Observation 1.9(c)).if a graph G contains a triangle,then x(G)>3.As the following result (proved by many)indicates,there are graphs G for which the lower bound for x(G)and the clique number (G)of G may differ significantly. Theorem 1.12.For every integer k2.there exists a triangle-free graph G with X(G)=k. bounds for the chromatic nu mber of a graph are concemed,the followngrsulves sucha bound in tems of the maximum degree of the graph. Theorem1.l3.For every graph G,x(G≤△(G+1. For each odd integer n>3,the connected graphs C and K have the property that x(Cn)=3 =A(Cn)+1 and x(K)n 4(Kn)1.The British mathematician Rowland Leonard Brooks showed that these two classes of graphs are the only connected graphs with this property. Theorem 1.14 (15)).If G is a connected graph that is neither an odd cycle nora complete&raph,then x(G)≤△(G 4 1 Introduction (or, more often, simply a k-coloring) of G. The minimum positive integer k for which G has a k-vertex coloring is called the chromatic number of G, denoted by .G/. For graphs of order n 3, it is immediate which graphs of order n have chromatic number 1, n or 2. Observation 1.9. If G is a graph of order n 3, then .a/ .G/ D 1 if and only if G is empty. .b/ .G/ D n if and only if G D Kn. .c/ .G/ D 2 if and only if G is a nonempty bipartite graph. An immediate consequence of Observation 1.9(c) is that .G/ 3 if and only if G contains an odd cycle. One of the most useful lower bounds for the chromatic number of a graph is stated below. Proposition 1.10. 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.10. Corollary 1.11. For every graph G, !.G/ .G/. By Corollary 1.11 (or, in fact, by Observation 1.9(c)), if a graph G contains a triangle, then .G/ 3. As the following result (proved by many) indicates, there are graphs G for which the lower bound for .G/ and the clique number !.G/ of G may differ significantly. Theorem 1.12. For every integer k 2, there exists a triangle-free graph G with .G/ D k. 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.13. For every graph G, .G/ .G/ C 1. For each odd integer n 3, the connected graphs Cn and Kn have the property that .Cn/ D 3 D .Cn/ C 1 and .Kn/ D n D .Kn/ 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.14 ([15]). If G is a connected graph that is neither an odd cycle nor a complete graph, then .G/ .G/.