I Introduction ofagraph was that be colored differently,resulting in proper edge colorings.Later,other restrictions were placed on edge colorings of graphs such as having distinct colors for its edges (so-called rainbow colorings)or a single color (a monochromatic coloring). In Tait's theorem that there exists a proper 4-coloring of the regions of a bridgeless cubic planar graph if and only if there exists a proper 3-coloring of the edges of the g of that a 4-coloring of the regi ns of such a gra aph car an be constructed h the ek olorin g the nts of the Klein f ar-group 4 assigning th an ed of G wh ch s the sum of the colors of its two incident regions.Sin e thes e colors are distinct,the edges are colored with the three nonzero elements ofxZ2. Tait's theorem can be considered as the beginning of a class of problems in which some type of coloring in a graph leads to another type of coloring in the graph.In this book we describe numerous edge colorings that have given rise to vertex colorings in some manner.For the most part,the edge colorings that we will encounter are unrestricted,that is,no condition is placed on the manner in which the edges may colored In Ch 8 and 9 ho it is the m st p pular type of edge with ling,namely proper edg e co The verte x colorngs that are genera d from edge colorings will have one of tw properties.The vertex colorings will either be proper or vertex-distinguishing (also called a rainbow coloring). Because proper edge colorings and proper vertex colorings are the most studied graph colorings and because it is results dealing with these colorings to which we will most often be referring,this chapter reviews these two coloring concepts as well as some of the theorems that have been obtained about them.We refer to the books otation and terminology not described in this vork 1.2 Proper Edge Colorings A proper edge coloring c of a nonempty graph G(a graph with edges)is a function c:E(G)S,where S is a set of colors (and so S=[k]or S =Z).with the proper)for every dohe coo called a k-edg teger or wh It is immediate for every nonempty graph G that x'(G)(G),where A(G) is the maximum degree of G.The most important theorem dealing with chromatic index is one obtained by the Russian mathematician Vadim Vizing. Theorem 1.1 ([78)).For every nonempty graph G. X(G≤△(G+1. 2 1 Introduction for assigning colors to the edges of a graph was that adjacent edges were required to be colored differently, resulting in proper edge colorings. Later, other restrictions were placed on edge colorings of graphs such as having distinct colors for its edges (so-called rainbow colorings) or a single color (a monochromatic coloring). In Tait’s theorem that there exists a proper 4-coloring of the regions of a bridgeless cubic planar graph if and only if there exists a proper 3-coloring of the edges of the graph, a proof that a 4-coloring of the regions of such a graph can result in a 3-coloring of its edges can be constructed by coloring the regions with the elements of the Klein four-group Z2Z2 and then assigning the color to an edge of G which is the sum of the colors of its two incident regions. Since these colors are distinct, the edges are colored with the three nonzero elements of Z2  Z2. Tait’s theorem can be considered as the beginning of a class of problems in which some type of coloring in a graph leads to another type of coloring in the graph. In this book we describe numerous edge colorings that have given rise to vertex colorings in some manner. For the most part, the edge colorings that we will encounter are unrestricted, that is, no condition is placed on the manner in which the edges may be colored. In Chaps. 8 and 9, however, it is the most popular type of edge colorings with which we will be dealing, namely proper edge colorings. The vertex colorings that are generated from edge colorings will have one of two properties. The vertex colorings will either be proper or vertex-distinguishing (also called a rainbow coloring). Because proper edge colorings and proper vertex colorings are the most studied graph colorings and because it is results dealing with these colorings to which we will most often be referring, this chapter reviews these two coloring concepts as well as some of the theorems that have been obtained about them. We refer to the books [19, 22] for graph theoretic notation and terminology not described in this work. 1.2 Proper Edge Colorings A proper edge coloring c of a nonempty graph G (a graph with edges) is a function c W E.G/ ! S, where S is a set of colors (and so S D Œk or S D Zk), with the property that c.e/ ¤ c.f/ for every two adjacent edges e and f of G. If the colors are chosen from a set of k colors, then c is called a k-edge coloring of G. The minimum positive integer k for which G has a k-edge coloring is called the chromatic index of G and is denoted by 0 .G/. It is immediate for every nonempty graph G that 0 .G/ .G/, where .G/ is the maximum degree of G. The most important theorem dealing with chromatic index is one obtained by the Russian mathematician Vadim Vizing. Theorem 1.1 ([78]). For every nonempty graph G, 0 .G/ .G/ C 1: