2 I Introduction Thereafter.the study of vertex colorings of graphs in general in which adiacent colored differently (pr r vertex colorings) has become a n r are of study in gra h theory Over the eyears,there been nume propert s requi red ertex colorings an n ways that certain graph colorings resulted from other graph colorings.In [76].various edge col orings were describe that result from vertex colorings of interest.In this book,this topic is continued However,the major goal of this book is to describe the kaleidoscopic nature of vertex colorings that have been studied in graphs. 1.2 Proper Vertex Colorings Aproper vertex coloring of a graph Gisafunctionc:V(G)S.where in our case S=因={L,2,.,k}orS=Z for some integer k≥2 such that c(a≠c(v） for every pair u.v of adjacent vertices of G.Since S=k,the coloring c is called a k-vertex coloring (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 y(a).Suppose that c is a k-coloring of a graph G.where each color is one of the inte gers 1.2. k say If V (1< i≤k)ishe set of ver tices in G colored i (whe re of thes y be class and the nonempty elements of empty set V&}produ partition of V(G).Because no two adjacent vertices of Gare assigned the same colo by c,each nonempty color class Vi(1 <i<k)is an independent set of vertices of G. For graphs of order n>3.it is immediate which graphs of order n have chromatic number 1.n or 2.A graph is empty if it has no edges;thus,a nonempty graph has one or more edges. Observation 1.2.1.If G is a graph of order n3.then (b)x(G)= (c)x(G)=2 if and only if G is a nonempty bipartite graph. An immediate consequence of Observation 1.2.1(c)is that x(G)>3 if and only if G contains an odd cycle. The union G=G +G2 of G]and G2 has vertex set V(G)=V(G)UV(G2) and edge set E(G)=E(G)UE(G2).The union G+G of two disjoint copies of G is denoted by 2G.Indeed.if a t copies of a graph H,then d、h verte V(G)= V(G) (Ga)and edge set E(G)=E(G)UE(Ga:u V(G1).vV(G2).The Cartesian product G of two graphs G and G commonly denoted by G G2 or Gi x G2,has vertex set V(G)=V(G1)x V(G2),where two distinct vertices (u.v)and (x.y)of GG2 are adjacent if either (1)u =x and vy EE(G2)or (2)v=y and ux EE(G).The definitions of the union,join or Cartesian product of two graphs can be extended to the union and join of any finite2 1 Introduction Thereafter, the study of vertex colorings of graphs in general in which adjacent vertices are colored differently (proper vertex colorings) has become a major area of study in graph theory. Over the years, there have been numerous changes in properties required of vertex colorings and in ways that certain graph colorings have resulted from other graph colorings. In [76], various edge colorings were described that result from vertex colorings of interest. In this book, this topic is continued. However, the major goal of this book is to describe the kaleidoscopic nature of vertex colorings that have been studied in graphs. 1.2 Proper Vertex Colorings A proper vertex coloring of a graph G is a function c W V.G/ ! S, where in our case, S D Œk D f1; 2; : : : ; kg or S D Zk for some integer k  2 such that c.u/ ¤ c.v/ for every pair u; v of adjacent vertices of G. Since jSj D k, the coloring c is called a k-vertex coloring (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/. Suppose that c is a k-coloring of a graph G, where each color is one of the integers 1; 2; : : : ; k say. If Vi (1  i  k) is the set of vertices in G colored i (where one or more of these sets may be empty), then each nonempty set Vi is called a color class and the nonempty elements of fV1; V2;:::; Vkg produce a partition of V.G/. Because no two adjacent vertices of G are assigned the same color by c, each nonempty color class Vi (1  i  k) is an independent set of vertices of G. For graphs of order n  3, it is immediate which graphs of order n have chromatic number 1, n or 2. A graph is empty if it has no edges; thus, a nonempty graph has one or more edges. Observation 1.2.1. 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.2.1(c) is that .G/  3 if and only if G contains an odd cycle. The union G D G1 C G2 of G1 and G2 has vertex set V.G/ D V.G1/ [ V.G2/ and edge set E.G/ D E.G1/ [ E.G2/. The union G C G of two disjoint copies of G is denoted by 2G. Indeed, if a graph G consists of k ( 2) disjoint copies of a graph H, then we write G D kH. The join G D G1 _ G2 of G1 and G2 has vertex set V.G/ D V.G1/ [ V.G2/ and edge set E.G/ D E.G1/ [ E.G2/ [ fuv W u 2 V.G1/; v 2 V.G2/g. The Cartesian product G of two graphs G1 and G2, commonly denoted by G1 G2 or G1 G2, has vertex set V.G/ D V.G1/ V.G2/, where two distinct vertices .u; v/ and .x; y/ of G1 G2 are adjacent if either (1) u D x and vy 2 E.G2/ or (2) v D y and ux 2 E.G1/. The definitions of the union, join or Cartesian product of two graphs can be extended to the union and join of any finite