SPRINGER BRIEFS IN MATHEMATICS Ping Zhang Color-Induced Graph Colorings ②Springer
123 SPRINGER BRIEFS IN MATHEMATICS Ping Zhang Color-Induced Graph Colorings
Preface The interest inedge colorings of graphs can be traced back to 1880 when the Scottish mathematician Peter Guthrie Tait attempted to solve the Four Color Problem with the aid of edge colorings.Despite the fact that Tait's approach was not successful. it initiated a new concept.In 1964,Vadim Vizing proved that the minimum number of colors needed to color the edges of a graph so that every two adjacent edges are ly (popedec)one of This 之二onl In recent decades,there has been great interest in edge colorings that give rise to vertex colorings in a variety of ways,which is the subject of this book.While we will be describing many ways in which edge colorings have induced vertex colorings he major results.problems,and conjectures that have arisen in our goal to give a detailed survey of these subjects.Indeed.it is our intention to of s nt colo avenues of research topics In Chap.1,we begin with a brief review of the well-known concepts of proper edge colorings and proper vertex colorings,including many fundamental results concerning them. In Chap.2,unrestricted edge colorings of graphs are considered whose colors the setNof positive int gers or a set[=1.2.....k for some such an edge colo h G a sum-defined ver is defined olor()ofv is the st of the edges inciden The dge coloring cis or irregular if the resulting vertex coloring chas the property that c() every pair u.v of distinct vertices of G.The minimum positive integer k for which a graph G has such a vertex-distinguishing edge coloring is the irregularity strength of G.In Chap.3,the corresponding coloring is considered in which the colors are taken from a set Z of integers modulo k
Preface The interest in edge colorings of graphs can be traced back to 1880 when the Scottish mathematician Peter Guthrie Tait attempted to solve the Four Color Problem with the aid of edge colorings. Despite the fact that Tait’s approach was not successful, it initiated a new concept. In 1964, Vadim Vizing proved that the minimum number of colors needed to color the edges of a graph so that every two adjacent edges are colored differently (proper edge colorings) is one of two numbers, namely either the maximum degree or the maximum degree plus one. This result led to an increased interest and study of edge colorings in graph theory, not only edge colorings that are proper but also edge colorings that are not. In recent decades, there has been great interest in edge colorings that give rise to vertex colorings in a variety of ways, which is the subject of this book. While we will be describing many ways in which edge colorings have induced vertex colorings and some of the major results, problems, and conjectures that have arisen in this area of study, it is not our goal to give a detailed survey of these subjects. Indeed, it is our intention to provide an organized summary of several recent coloring concepts and topics that belong to this area of study, with the hope that this may suggest new avenues of research topics. In Chap. 1, we begin with a brief review of the well-known concepts of proper edge colorings and proper vertex colorings, including many fundamental results concerning them. In Chap. 2, unrestricted edge colorings of graphs are considered whose colors are elements of the set N of positive integers or a set Œk D f1; 2; : : : ; kg for some positive integer k. From such an edge coloring c of a graph G, a sum-defined vertex coloring c0 is defined, that is, for each vertex v of G, the color c0 .v/ of v is the sum of the colors of the edges incident with v. The edge coloring c is vertex-distinguishing or irregular if the resulting vertex coloring c0 has the property that c0 .u/ ¤ c0 .v/ for every pair u; v of distinct vertices of G. The minimum positive integer k for which a graph G has such a vertex-distinguishing edge coloring is the irregularity strength of G. In Chap. 3, the corresponding coloring is considered in which the colors are taken from a set Zk of integers modulo k. v
vi Preface Chapter 4 also deals with unrestricted edge coloringsc of graphs but here the induced vertex coloring is defined so that the color c(v)of a vertex v is the set of colors of its incident edges.In Chap.5,the emphasis changes from vertex colorings that are set-defined to those that are multiset-defined.In both cases.the induced vertex colorings c'are vertex-distinguishing. In Chap.6.unrestricted edge colorings c of graphs are once again considered but in this case the induced vertex coloringscare neighbor-distinguishing,that is (≠c'(w)fore ery two adiacent vertices u nd v.In this ch apter. d hoth re olors bel ng is sum-defined and the other where)is mul Itiset-defined.Chapter 7is devoted to unrestricted edge colorings of graphs whose colors are elements of Z of integers modulo k that induce a sum-defined,neighbor-distinguishing vertex coloring. In Chap.8.both proper and unrestricted edge colorings are considered,and the vertex colorings are set-defined,using elements of [k]as colors.In Chap.9.the edge colorings are proper and the vertex colorings considered are sum-defined,using elements of[as colors.In these two chapters,the properties of being vertex. distinguishi and neighbor-distinguishing ar both des bed.Cha nds with edge colo which are proper edge colorin use the t ar sum-defined The following table summarizes all types of edge colorings considered in this book and the resulting vertex colorings.In particular,the table describes,in each chapter: 1.the condition placed on the edge coloring 2 the sets from thedkinion which the edge colors are selected. f the colors,and Chapter 1:Introduction Chapter 2:The Irregularity Strength of a Graph Unrestricted Edge Colorings.N.Sum-defined.Vertex-Distinguishing Chapter 3:Modular Sum-defined,Irregular Colorings ined,Vertex-Distinguishing Chapter 4:Se -Defined Irregula Unrestricted Edg ge Colorings.N.Set-definec Vertex-Distinguishing. Chapter 5:Multiset-Defined Irregular Colorings Unrestricted Edge Colorings.N.Multiset-defined.Vertex-Distinguishing Chapter 6:Sum-Defined Neighbor-Distinguishing Colorings Unrestricted Edge Colorings.N.Sum-defined,Neighbor-Distinguishing. Chapter 7:Modular Sum-Defined Neighbor-Distinguishing Colorings Unrestricted Edge Colorings.Sum-defined,Neighbo Distinguishing
vi Preface Chapter 4 also deals with unrestricted edge colorings c of graphs but here the induced vertex coloring is defined so that the color c0 .v/ of a vertex v is the set of colors of its incident edges. In Chap. 5, the emphasis changes from vertex colorings that are set-defined to those that are multiset-defined. In both cases, the induced vertex colorings c0 are vertex-distinguishing. In Chap. 6, unrestricted edge colorings c of graphs are once again considered but in this case the induced vertex colorings c0 are neighbor-distinguishing, that is, c0 .u/ ¤ c0 .v/ for every two adjacent vertices u and v. In this chapter, two vertex colorings c are defined, both where the colors belong to a set Œk, one where c0 .v/ is sum-defined and the other where c0 .v/ is multiset-defined. Chapter 7 is devoted to unrestricted edge colorings of graphs whose colors are elements of Zk of integers modulo k that induce a sum-defined, neighbor-distinguishing vertex coloring. In Chap. 8, both proper and unrestricted edge colorings are considered, and the vertex colorings are set-defined, using elements of Œk as colors. In Chap. 9, the edge colorings are proper and the vertex colorings considered are sum-defined, using elements of Œk as colors. In these two chapters, the properties of being vertexdistinguishing and neighbor-distinguishing are both described. Chapter 9 ends with a discussion of so-called twin edge colorings, which are proper edge colorings that use the elements of Zk as colors and that induce proper vertex colorings that are sum-defined. The following table summarizes all types of edge colorings considered in this book and the resulting vertex colorings. In particular, the table describes, in each chapter: 1. the condition placed on the edge coloring, 2. the sets from which the edge colors are selected, 3. the definition of the vertex colors, and 4. the property required of the resulting vertex coloring. Chapter 1: Introduction Chapter 2: The Irregularity Strength of a Graph Unrestricted Edge Colorings, N, Sum-defined, Vertex-Distinguishing. Chapter 3: Modular Sum-defined, Irregular Colorings Unrestricted Edge Colorings, Zk, Sum-defined, Vertex-Distinguishing. Chapter 4: Set-Defined Irregular Colorings Unrestricted Edge Colorings, N, Set-defined, Vertex-Distinguishing. Chapter 5: Multiset-Defined Irregular Colorings Unrestricted Edge Colorings, N, Multiset-defined, Vertex-Distinguishing. Chapter 6: Sum-Defined Neighbor-Distinguishing Colorings Unrestricted Edge Colorings, N, Sum-defined, Neighbor-Distinguishing. Chapter 7: Modular Sum-Defined Neighbor-Distinguishing Colorings Unrestricted Edge Colorings, Zk, Sum-defined, Neighbor-Distinguishing.
Preface Chapter 8:Strong Edge Colorings 8.1.Proper Edge Colorings,N.Set-defined,Vertex-Distinguishing. 8.2.Proper and Unrestricted Edge Colorings,N.Set-defined,Vertex-Distinguishing. 8.3.Proper Edge Colorings,N.Set-defined,Neighbor-Distinguishing. Chapter 9:Sum-Defined Colorings by Proper Edge Colorings 9.1.Proper Edge Colorings.N.Sum-defined,Vertex- 9..Proper Edge Colorings. stingu 9.3.Proper Edge Colorings.Z.Sum-defined,Neighbor-Distinguishing Kalamazoo,MI,USA Ping Zhang
Preface vii Chapter 8: Strong Edge Colorings 8.1. Proper Edge Colorings, N, Set-defined, Vertex-Distinguishing. 8.2. Proper and Unrestricted Edge Colorings, N, Set-defined, Vertex-Distinguishing. 8.3. Proper Edge Colorings, N, Set-defined, Neighbor-Distinguishing. Chapter 9: Sum-Defined Colorings by Proper Edge Colorings 9.1. Proper Edge Colorings, N, Sum-defined, Vertex-Distinguishing. 9.2. Proper Edge Colorings, N, Sum-defined, Neighbor-Distinguishing. 9.3. Proper Edge Colorings, Zk, Sum-defined, Neighbor-Distinguishing. Kalamazoo, MI, USA Ping Zhang
Acknowledgements With pleasure.the author thanks Gary Chartrand for the advice and informatior he kindy suppied on may topics described n this book thanks th iewers for able i and s vided with the first draft of this inally,th because of all of you that an improved book resulted. ix
Acknowledgements With pleasure, the author thanks Gary Chartrand for the advice and information he kindly supplied on many topics described in this book. In addition, the author thanks the reviewers for the valuable input and suggestions they provided with the first draft of this manuscript. Finally, the author is very grateful to Razia Amzad, SpringerBriefs editor, for her kindness and encouragement in writing this book. It is because of all of you that an improved book resulted. ix