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:
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 coloring
1.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
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/.
Chapter 2 The Irregularity Strength of a Graph Throughout Chaps.2-7,we will be concerned with connected graphs G of order 3 and size m and an unrestricted edge coloring of G.that is,no condition is in which c olors re assigned to the edge s of G. The edge colorings inducing vertex colorings that have attracted the most attention are those where the vertex colorings are either vertex-distinguishing or neighbor-distinguishing.In this chapter,we consider a particular example of the first of these. A nontrivial graph has been called irregular if its vertices have distinct degrees It is well known that there is no such graph;that is,no graph is irregular.This observation led to a concept introduced by Gary Chartrand at the 250th Anniversary of Graph Theory Conference held at Indiana University-Purdue University For Way 86 ected graph G.a weighring w of G is an assignm ent of number (usually positive integers)to the edges of G.where w(e)denotes the weight of a edge e of G.This then converts G into a weighted graph in which the (weighted) degree of a vertex v is defined as the sum of the weights of the edges incident with v. A weighted graph G is then irregular if the vertices of G have distinct degrees.Later this concept was viewed in another setting. 2.1 Sum-Defined Vertex Colorings:Irregularity Strength Rather than consider connected graphs G of order at least 3 whose edges are assigned weights,resulting in irregular weighted graphs,we can view this as vertex- distinguishing edge colorings of G where the induced vertex coloring is sum-defined and where then the vertices of G have distinct colors.Such vertex colorings are also referred to as rainbow vertex colorings. Ping Zhang 2015 lorings.SpringerBriefs in Mathematics
Chapter 2 The Irregularity Strength of a Graph Throughout Chaps. 2–7, we will be concerned with connected graphs G of order n 3 and size m and an unrestricted edge coloring of G, that is, no condition is placed on the manner in which colors are assigned to the edges of G. The unrestricted edge colorings inducing vertex colorings that have attracted the most attention are those where the vertex colorings are either vertex-distinguishing or neighbor-distinguishing. In this chapter, we consider a particular example of the first of these. A nontrivial graph has been called irregular if its vertices have distinct degrees. It is well known that there is no such graph; that is, no graph is irregular. This observation led to a concept introduced by Gary Chartrand at the 250th Anniversary of Graph Theory Conference held at Indiana University-Purdue University Fort Wayne in 1986. For a connected graph G, a weighting w of G is an assignment of numbers (usually positive integers) to the edges of G, where w.e/ denotes the weight of an edge e of G. This then converts G into a weighted graph in which the (weighted) degree of a vertex v is defined as the sum of the weights of the edges incident with v. A weighted graph G is then irregular if the vertices of G have distinct degrees. Later this concept was viewed in another setting. 2.1 Sum-Defined Vertex Colorings: Irregularity Strength Rather than consider connected graphs G of order at least 3 whose edges are assigned weights, resulting in irregular weighted graphs, we can view this as vertexdistinguishing edge colorings of G where the induced vertex coloring is sum-defined and where then the vertices of G have distinct colors. Such vertex colorings are also referred to as rainbow vertex colorings. © Ping Zhang 2015 P. Zhang, Color-Induced Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-20394-2_2 5
2 The Irregularity Strength of a Graph We now formally define such vertex-distinguishing edge colorings.Let N denote the set of positive integers and let E denote the set of edges incident with a vertex v in a graph G.An unrestricted edge coloring c:E(G)N induces a vertex coloring c:V(G→.defined by c(v)=c(e)for each vertex v of G. (2.1) EE. ected graph and(G)Nbe vertex coloring defined Proof.Let E(G)=e1,e2.....em).Since c'w)=2∑c(e) rev(G is even,there exists an even number of vertices of odd color. While no connected graph G of order 3 or more.To see this,let E(G)=fe1.e2.....em where then m>2 and let c be the edge coloring of G defined by c(ei)=2-1 for 1<i<m.Since no two vertices are incident with the same set of edges,c induces a rainbow vertex coloring.This edge coloring shows that there is always a vertex- onnected aph of size m2 where the largest color exist g edge coloringso of a graph of size m who ose large bly le than 2 For a connected graph G of size m2.the minimum of the largest colors used among the vertex-distinguishing edge colorings of G is called the irregularity strength of G and is denoted by s(G).(The strength of a multigraph M is the maximum number of parallel edges joining two vertices of M.)Therefore,for a connected graph G of order at least 3,there exists an edge coloring c:E(G) k1=1.2. .k)for every integer k with k =s(G)such that the induced (sum- defined) distingu shing but there is no ach edge coloring c:E(G) →因wi for any m with I 1≤k<s(G). Since ne rregular,it follows th very connected graph of order at least 3 must have irregularity strength at least 2.It is well known that there is exactly one connected graph Gn of order n for each n>2 containing exactly two vertices having the same degree.All of these graphs have irregularity strength 2. Proposition 2.2.If Gn is the unique connected graph of order n 3 containing exactly two vertices of equal degree,then s(G)=2. Proof.As mentioned above,s(G)>2 for every integer n2.Each such graph G n be de s h aving vertex set V(Gn)=1.v2.....vE(G if and only if i+jsn+1.Consequently
6 2 The Irregularity Strength of a Graph We now formally define such vertex-distinguishing edge colorings. Let N denote the set of positive integers and let Ev denote the set of edges incident with a vertex v in a graph G. An unrestricted edge coloring c W E.G/ ! N induces a vertex coloring c0 W V.G/ ! N, defined by c0 .v/ D X e2Ev c.e/ for each vertex v of G: (2.1) Proposition 2.1. Let G be a nontrivial connected graph and let c W E.G/ ! N be an edge coloring of G, where c0 W V.G/ ! N is the induced vertex coloring defined in (2.1). Then there exists an even number of vertices of odd color. Proof. Let E.G/ D fe1; e2;:::; emg. Since X v2V.G/ c0 .v/ D 2 Xm iD1 c.ei/ is even, there exists an even number of vertices of odd color. While no edge coloring of the graph K2 can induce a rainbow vertex coloring defined in this manner, there is a vertex-distinguishing edge coloring for every connected graph G of order 3 or more. To see this, let E.G/ D fe1; e2;:::; emg where then m 2 and let c be the edge coloring of G defined by c.ei/ D 2i1 for 1 i m. Since no two vertices are incident with the same set of edges, c induces a rainbow vertex coloring. This edge coloring shows that there is always a vertexdistinguishing edge coloring of a connected graph of size m 2 where the largest color used is 2m1. In general, there exist vertex-distinguishing edge colorings of a graph of size m whose largest color is considerably less than 2m1. For a connected graph G of size m 2, the minimum of the largest colors used among the vertex-distinguishing edge colorings of G is called the irregularity strength of G and is denoted by s.G/. (The strength of a multigraph M is the maximum number of parallel edges joining two vertices of M.) Therefore, for a connected graph G of order at least 3, there exists an edge coloring c W E.G/ ! Œk D f1; 2; : : : ; kg for every integer k with k s.G/ such that the induced (sumdefined) vertex coloring c0 is vertex-distinguishing but there is no such edge coloring c W E.G/ ! Œk with this property for any integer k with 1 k < s.G/. Since no nontrivial graph is irregular, it follows that every connected graph of order at least 3 must have irregularity strength at least 2. It is well known that there is exactly one connected graph Gn of order n for each n 2 containing exactly two vertices having the same degree. All of these graphs have irregularity strength 2. Proposition 2.2. If Gn is the unique connected graph of order n 3 containing exactly two vertices of equal degree, then s.Gn/ D 2. Proof. As mentioned above, s.Gn/ 2 for every integer n 2. Each such graph Gn can be described as having vertex set V.Gn/ D fv1; v2;:::;vng where vivj 2 E.Gn/ if and only if i C j n C 1. Consequently,