SPRINGER BRIEFS IN MATHEMATICS Ping Zhang A Kaleidoscopic View of Graph Colorings ②Springer
123 SPRINGER BRIEFS IN MATHEMATICS Ping Zhang A Kaleidoscopic View of Graph Colorings
PrefaceIt is the origin of the Four Color Problem by Francis Guthrie in 1852 that led tocoloring maps and then to coloring planarlotonlvcosregions butcoloring its vertices and edges as well.In 1880, when Peter Guthrie Tait attemptedto solvetheFour Color Problem,it wasknown that theFourColor Problem could besolvedforall planargraphsifitcould besolvedforall3-regular bridgeless planargraphs. Tait was successful in showing that the Four Color Problem could be solvedin the affrmative if it could be shown that the edges of every 3-regular bridgelessplanar graph could be colored with three colors in such a way that no two adjacentedges arecolored thesame.Hedid thisby showingthat such an edge coloring ofthese planar graphs led to a coloring of theirregions with four or few colors so thatcolored the same, and conversely. While Tait's approachnoto3acnever ledtoa solution of the Four Color Problem, his idea of how one coloring of ang of value has opened up a large variety of coloringgraph can lead to another colorinproblems. The major goal of this book is to describe the kaleidoscopic nature ofvarious colorings that have been studied in graphs.aphcoloringsthathosledtootherhere.have.apOTcolorings of interest in a variety of ways. In the author's book Color-Induced GraphColorings, various edge colorings were described that result from vertex coloringsof interest. In this book, this topic is continued. While we will be describing manyways that edge or vertex colorings have given rise to other colorings and discussingsome of the major results.problems and conjectures that haveresulted in this areaof study,it is not our goal togivea detailed survey of these subjects.Indeed,it isour intention to provide an organized summary of several recent coloring conceptsandpicsthatbongthsareasudywithhehpethatthsmaysugestnwavenuesofresearchtopics.In Chap.1,thebackground forbasic colorings concepts is reviewed.Thereisber of other concepts and results that will be encounteredalsoareviewofanumbthroughout the book. In Chaps.2 and 3, edge colorings of graphs are discussed thatlead to vertex colorings defined in terms of sets and multisets of the colors of the
Preface It is the origin of the Four Color Problem by Francis Guthrie in 1852 that led to coloring maps and then to coloring planar graphs—not only coloring its regions but coloring its vertices and edges as well. In 1880, when Peter Guthrie Tait attempted to solve the Four Color Problem, it was known that the Four Color Problem could be solved for all planar graphs if it could be solved for all 3-regular bridgeless planar graphs. Tait was successful in showing that the Four Color Problem could be solved in the affirmative if it could be shown that the edges of every 3-regular bridgeless planar graph could be colored with three colors in such a way that no two adjacent edges are colored the same. He did this by showing that such an edge coloring of these planar graphs led to a coloring of their regions with four or few colors so that no two adjacent regions are colored the same, and conversely. While Tait’s approach never led to a solution of the Four Color Problem, his idea of how one coloring of a graph can lead to another coloring of value has opened up a large variety of coloring problems. The major goal of this book is to describe the kaleidoscopic nature of various colorings that have been studied in graphs. Over the years, there have been many graph colorings that have led to other graph colorings of interest in a variety of ways. In the author’s book Color-Induced Graph Colorings, various edge colorings were described that result from vertex colorings of interest. In this book, this topic is continued. While we will be describing many ways that edge or vertex colorings have given rise to other colorings and discussing some of the major results, problems and conjectures that have resulted 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, the background for basic colorings concepts is reviewed. There is also a review of a number of other concepts and results that will be encountered throughout the book. In Chaps. 2 and 3, edge colorings of graphs are discussed that lead to vertex colorings defined in terms of sets and multisets of the colors of the v
Prefaceedges. This leads to colorings called binomial colorings, kaleidoscopic coloringsand majestic colorings.In Chaps.4 and 5, we discuss vertex colorings that induce a variety of edgecolorings, which are related to the well-known graceful labelings and harmoniouslabelingsIn Chap. 6, region colorings of planar graphs are discussed, where regions sharinga common boundary edge are required to be colored differently. Several regioncolorings are described that not only distinguish every pair of adiacent regions butwhich potentially require the use of fewer colors than a standard region coloringThis, in turn, leads to vertex colorings of graphs in general, discussed in Chaps.10, which are, respectively,deined in terms of sets, multisets, distances, and sumsofcolors.InChap.Lltwo combinatorial problemsaredescribedJeadingotwo grapl, which are also discussed in this chapter. In Chap.12, twocoloringproblemBanquet Seating Problems are described, each of which can be modeled by agraphand suggests two types of colorings of the graph. This gives rise to two vertexoringsgaphsingawhhathpsdicussediChaps3andKalamazoo,ML USAPing Zhang21 December 2015
vi Preface edges. This leads to colorings called binomial colorings, kaleidoscopic colorings, and majestic colorings. In Chaps. 4 and 5, we discuss vertex colorings that induce a variety of edge colorings, which are related to the well-known graceful labelings and harmonious labelings. In Chap. 6, region colorings of planar graphs are discussed, where regions sharing a common boundary edge are required to be colored differently. Several region colorings are described that not only distinguish every pair of adjacent regions but which potentially require the use of fewer colors than a standard region coloring. This, in turn, leads to vertex colorings of graphs in general, discussed in Chaps. 7– 10, which are, respectively, defined in terms of sets, multisets, distances, and sums of colors. In Chap. 11, two combinatorial problems are described, leading to two graph coloring problems, which are also discussed in this chapter. In Chap. 12, two Banquet Seating Problems are described, each of which can be modeled by a graph and suggests two types of colorings of the graph. This gives rise to two vertex colorings of graphs in general, which are the topics discussed in Chaps. 13 and 14. Kalamazoo, MI, USA Ping Zhang 21 December 2015
Acknowledgements With pleasure.the author thanks Gary Chartrand for the advice and informatior he kindly supplied on many topics described in this book.In addition,the author thanks the and e tions on the first draft of this o her kindnend encouragement in inhi book that an improved book resulted
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 reviewer for the valuable input and suggestions on the first draft of this manuscript. Finally, the author is so 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. vii
Contents 1 Introduction. 1.1 Graph Colorings.......................... 1.2 Proper Vertex Colorings. 2 1.3 Proper Edge Colorings. 4 1.4 5 1.5 ATheorem fro m Dise 3““+440”4。+44+44”44““4+0+4 5 2 Binomial Edge Colorings. 1 2. Strong Edge Colorings.... 2.2 Proper k-Binomial-Colorable Graphs.... 9 2.3 Unrestricted k-Binomial-Colorable Graphs..................... 14 3 Kaleidoscopic Edge Colorings. 19 3.1 Introduction 19 3 nplete Kaleidosco 13 3-Kaleidosc of M Order 34 Maiestic Edge Colorings. 32 Graceful Vertex Colorings. 35 41 Graceful Labelings.… 4. The Graceful Chromatic Number of a Graph....................... 36 4.3 Graceful Chromatic Numbers of Some Well-Known Graphs...... % 4.4 The Graceful Chromatic Numbers of Trees.. Harmonious Vertex Colorings.. 1 1ng5t+tte…4tt4t。+4。 5 armonio 53 Colorings… Harmonic Colorings....... 3509 6 A Map Coloring Problem.... 6.1 A New Look at Map Colorings................... 7 Set Colorings 67 7.1 Set Chromatic Number. ix
Contents 1 Introduction ................................................................. 1 1.1 Graph Colorings...................................................... 1 1.2 Proper Vertex Colorings ............................................. 2 1.3 Proper Edge Colorings ............................................... 4 1.4 Eulerian Graphs and Digraphs....................................... 5 1.5 A Theorem from Discrete Mathematics............................. 5 2 Binomial Edge Colorings .................................................. 7 2.1 Strong Edge Colorings ............................................... 7 2.2 Proper k-Binomial-Colorable Graphs ............................... 9 2.3 Unrestricted k-Binomial-Colorable Graphs ......................... 14 3 Kaleidoscopic Edge Colorings............................................. 19 3.1 Introduction........................................................... 19 3.2 Complete Kaleidoscopes............................................. 21 3.3 3-Kaleidoscopes of Maximum Order................................ 27 3.4 Majestic Edge Colorings............................................. 32 4 Graceful Vertex Colorings................................................. 35 4.1 Graceful Labelings ................................................... 35 4.2 The Graceful Chromatic Number of a Graph ....................... 36 4.3 Graceful Chromatic Numbers of Some Well-Known Graphs...... 40 4.4 The Graceful Chromatic Numbers of Trees......................... 45 5 Harmonious Vertex Colorings............................................. 53 5.1 Harmonious Labelings ............................................... 53 5.2 Harmonious Colorings ............................................... 55 5.3 Harmonic Colorings.................................................. 59 6 A Map Coloring Problem .................................................. 63 6.1 A New Look at Map Colorings...................................... 63 7 Set Colorings ................................................................ 67 7.1 Set Chromatic Number............................................... 67 ix