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 finite
2 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
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:
4 1.3 Proper Edge Colorings A Sisasetof c rs(and typically S =Zk for som ≥2，wihh property that c(e)≠ c(f)for every two adja 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 x'(G). It is immediate for every nonempty graph G that x'(G)>A(G).The most important theorem dealing with chromatic index is one obtained by the Russian mathematician Vadim Vizing. Theorem 1.3.1 ([741).For every nonempty graph G. X(G≤△(G+1. As a result of Vizing's theorem,the chromatic index of every nonempty graph G is one of two numbers,namely△(Gor△(G)+1.A graph G with x'(G)=△(G is called a class one graph while a graph Gwith x'(G)=A(G)+1 is called a class grapThe chromatic index of complete graphs is given in the following result. Theorem 1.3.2.For each integer n 2. I'(Kn)=n-1 ifn is even n if n is odd. Therefore.K,is a class one graph if n is even and is a class two graph if n is odd. The fact that K is a class one graph if and only if n is even is also a consequence of the following. An immediate consequence of this result is stated next. Corollary 1.3.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.3.5 ([48)).Every bipartite graph is a class one graph If a graphGofodd order has sufficiently many edges.then must be a classtw graph.A graph G of order n and size m is called overfull if m> △(G)n/2.fC 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.3.6.Every overfull graph is a class two graph
4 1 Introduction 1.3 Proper Edge Colorings A proper edge coloring c of a nonempty graph G is a function c W E.G/ ! S, where S is a set of colors (and typically S D Œk or S D Zk for some integer k 2), 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/. The most important theorem dealing with chromatic index is one obtained by the Russian mathematician Vadim Vizing. Theorem 1.3.1 ([74]). For every nonempty graph G, 0 .G/ .G/ C 1: 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.3.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.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.3.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.3.5 ([48]). Every bipartite graph 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.3.6. Every overfull graph is a class two graph.
1.5 ATheorem from Discrete Mathematics 5 1.4 Eulerian Graphs and Digraphs A circuit in a nontrivial connected graph G that contains every edge of G (necessarily exactly once)is an Eulerian circuit in a graph.A connected graph G is Eulerian if G contains an Eulerian circuit.The following characterization of Eulerian graphs is attributed to Leonhard Euler. Theorem 1.4.1 ([31)).A nontrivial connected graph G is Eulerian if and only if every vertex ofG has even degree These concepts dealing with raphs as well.Ar Eulerian ci rcir mn a con at contains every arc of D.A connected digraph that contains an Eulerian circuit is an Euleriar digraph.As with the characterization of Eulerian graphs in Theorem 1.4.1,the characterization of Eulerian digraphs stated next is given in terms of the digraph analogues of'degrees'.The ourdegree odv of a vertex v in a digraph D is the number of arcs incident with and directed away from v,while the indegree idv ofis the number of ares incident with and directed towards. For example,since odv=idv for every vertex v of the digraph D of Fig.1.1,it is Eulerian and(v1.v2.v3.v7.v6.v2.v4.v6.vs,v.v)is an Eulerian circuit of D. 1.5 A Theorem from Discrete Mathematics t ome basic factsn mthemihogh on,there is one result that we wil encounter so c ten that it valuable to state here at the beginning.This result deals with combinations with repetition. Theorem 1.5.1.Let A be a multiset containing t different kinds of elements,where there are at least r elements of each kind.The number of different selections of r elements from Ais(t-l） Fig.1.1 An Eulerian digraph D
1.5 A Theorem from Discrete Mathematics 5 1.4 Eulerian Graphs and Digraphs A circuit in a nontrivial connected graph G that contains every edge of G (necessarily exactly once) is an Eulerian circuit in a graph. A connected graph G is Eulerian if G contains an Eulerian circuit. The following characterization of Eulerian graphs is attributed to Leonhard Euler. Theorem 1.4.1 ([31]). A nontrivial connected graph G is Eulerian if and only if every vertex of G has even degree. These concepts dealing with graphs have analogues for digraphs as well. An Eulerian circuit in a connected digraph D is a directed circuit that contains every arc of D. A connected digraph that contains an Eulerian circuit is an Eulerian digraph. As with the characterization of Eulerian graphs in Theorem 1.4.1, the characterization of Eulerian digraphs stated next is given in terms of the digraph analogues of ‘degrees’. The outdegree od v of a vertex v in a digraph D is the number of arcs incident with and directed away from v, while the indegree id v of v is the number of arcs incident with and directed towards v. Theorem 1.4.2. Let D be a nontrivial connected digraph. Then D is Eulerian if and only if od v D id v for every vertex v of D. For example, since od v D id v for every vertex v of the digraph D of Fig. 1.1, it is Eulerian and .v1; v2; v3; v7; v6; v2; v4; v6; v5; v4; v1/ is an Eulerian circuit of D. 1.5 A Theorem from Discrete Mathematics While we will use some basic facts and results from discrete mathematics throughout our discussion, there is one result that we will encounter so often that it is valuable to state here at the beginning. This result deals with combinations with repetition. Theorem 1.5.1. Let A be a multiset containing ` different kinds of elements, where there are at least r elements of each kind. The number of different selections of r elements from A is rC`1 r . Fig. 1.1 An Eulerian digraph D ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ................................................. .................................................. ................................................ .................................................. .......... . . .. .. ........... . ......... ......... . . . . .. .. ........... ........ .......... . . ......................... .......... . . ......................... ... ... ... ... .......... ... ... ... .... ................................... ... .......... ....... ....... ...... ...... ............. .... . . . . . . .. .. .... ....... ... ... .......... .. .. .. .................... ............ ................... .. .. .. . v3 v4 v1 v2 v5 v6 v7 D :
6 I Introduction rate heorem.suppose thatsmultistonta kinds of ele ents sav 123.4 elements of each kind For example,perhaps. A={1,1,1,2,2,2,333.4.4.4 骨e2 following multisets: A1={1,1,1,A2=2,2,2.A3={3,3,3.A4={4,4,4 A5={1,1,2,A6={1,1,3,A7={1,1,4,A8={2,2,1 Ag={2,2.3,A10={2.2.4},A11={3,3.1h,A12={3,3,2} A3={3,3,4.A14={4,4.1A15={4,4,2头，A16={4,4,3} A7={1,2,3头A18={1,2.4.A19={1,3,4.A20=2,3,4}
6 1 Introduction To illustrate Theorem 1.5.1, suppose that A is a multiset containing four different kinds of elements, say 1; 2; 3; 4, and there are at least three elements of each kind. For example, perhaps, A D f1; 1; 1; 2; 2; 2; 3; 3; 3; 4; 4; 4g: Hence, ` D 4 and r D 3. By Theorem 1.5.1, the number of selections of r D 3 elements from A is rC`1 r D 3C41 3 D 6 3 D 20. The 20 selections here are the following multisets: A1 D f1; 1; 1g; A2 D f2; 2; 2g; A3 D f3; 3; 3g; A4 D f4; 4; 4g A5 D f1; 1; 2g; A6 D f1; 1; 3g; A7 D f1; 1; 4g; A8 D f2; 2; 1g A9 D f2; 2; 3g; A10 D f2; 2; 4g; A11 D f3; 3; 1g; A12 D f3; 3; 2g A13 D f3; 3; 4g; A14 D f4; 4; 1g; A15 D f4; 4; 2g; A16 D f4; 4; 3g A17 D f1; 2; 3g; A18 D f1; 2; 4g; A19 D f1; 3; 4g; A20 D f2; 3; 4g: