1.3 Proper Vertex Colorings 3 As a result of Vizing's theorem,the chromatic index of every nonempty graph namely (G)orA(G)+1.A graphG with gr pwhile a graph wth △(G+ alled a clas wo graph.The chromatic index of complete graphs is given in the owing result Theorem 1.2.For each integer n≥2， (n-1 ifn is even X(K)=n ifn is odd. Therefore,K is a class one graph ifn is even and is aclass two graph if n is odd. The fact that K is a class one graph if and only if nis even is also a consequence of the following. Theorem 1.3.A regular graph G is a elass one graph if and only if G is 1-factorable. An immediate consequence of this result is stated next. Corollary 1.4.Every regular graph of odd order is a class two graph. The next two results describe classes of graphs that are class one graphs.The first theorem is due to Denes Konig. Theorem 1.5 ([691).Every bipartite graph is a class one graph The following result is due to Jean-Claude Fournier. Theorem 1.6 ([431).Let G be an nonempty graph.If the subgraph of G induced by the vertices of degree A(G)is a forest,then G is a class one graph. From this,we have the following corollary Corollary 1.7 ([43D).If G is a graph in which no two vertices of maximum degree are adjacent,then G is a class one graph. If a graph Gofodd order has sufficiently many edges,then Gmust be a class two graph.A graph G of order n and size m is called overfull if m >A(G)n/2].If G has even order n.then m <A(G)n/2]and so G is not overfull.On the other hand, a graph of odd order may be overfull. Theorem 1.8.Every overfull graph is a class two graph. 1.3 Proper Vertex Colorings A proper vertex coloring of a graph G is a function c':V(G)S,where in our case.S C N or S=Z&for some integer k 2 such that c'(u)c'(v)for every pair u.v of adjacent vertices of G.If S =k,then c'is called a k-vertex coloring1.3 Proper Vertex Colorings 3 As a result of Vizing’s theorem, the chromatic index of every nonempty graph G is one of two numbers, namely .G/ or .G/ C 1. A graph G with 0 .G/ D .G/ is called a class one graph while a graph G with 0 .G/ D .G/ C 1 is called a class two graph. The chromatic index of complete graphs is given in the following result. Theorem 1.2. For each integer n 2, 0 .Kn/ D n  1 if n is even n if n is odd. Therefore, Kn is a class one graph if n is even and is a class two graph if n is odd. The fact that Kn is a class one graph if and only if n is even is also a consequence of the following. Theorem 1.3. A regular graph G is a class one graph if and only if G is 1-factorable. An immediate consequence of this result is stated next. Corollary 1.4. Every regular graph of odd order is a class two graph. The next two results describe classes of graphs that are class one graphs. The first theorem is due to Denés König. Theorem 1.5 ([69]). Every bipartite graph is a class one graph. The following result is due to Jean-Claude Fournier. Theorem 1.6 ([43]). Let G be an nonempty graph. If the subgraph of G induced by the vertices of degree .G/ is a forest, then G is a class one graph. From this, we have the following corollary. Corollary 1.7 ([43]). If G is a graph in which no two vertices of maximum degree are adjacent, then G is a class one graph. If a graph G of odd order has sufficiently many edges, then G must be a class two graph. A graph G of order n and size m is called overfull if m > .G/bn=2c. If G has even order n, then m .G/bn=2c and so G is not overfull. On the other hand, a graph of odd order may be overfull. Theorem 1.8. Every overfull graph is a class two graph. 1.3 Proper Vertex Colorings A proper vertex coloring of a graph G is a function c0 W V.G/ ! S, where in our case, S  N or S D Zk for some integer k 2 such that c0 .u/ ¤ c0 .v/ for every pair u; v of adjacent vertices of G. If jSj D k, then c0 is called a k-vertex coloring