《图论》课程教学资源（书籍文献）A Kaleidoscopic View of Graph Colorings

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

Contents 7.2 3 The Set Chromatic Numbers of Some Classes of Graphs. 69 Lower Bounds for the Set Chromatic Number....... Multiset Colorings............. 8.1 Multiset Chromatic Number......... 8.2 Complete Multipartite Graphs 83 Graphs with Prescribed Order and Multiset Chromatic Number.. 多 8.4 Multiset Colorings Versus Set Colorings. Metric Colorings..... Metric Chre 9.3 Bounds for the Metric Chromatic Number of a Graph............. 9.4 Metric Colorings Versus Other Colorings......................... % 10 Sigma Colorings 5 10.1 Sigma Chromatic Number. 9 10.2 Sigma Colorings Versus Multiset Colorings Value a nd ra 10.4 ge...................................... r Colorings Problems 101 Modular Colorings. 11.1 ACheckerboard Problem. 11.2 Modular Colorings ................................ 105 11.3 A Lights Out Problem.. 110 11.4 Closed Modular Colorings 111 2 A Ban et Seating Problem 12.1 ts at a Cir ular Table 117 12.2 Modeling the Seating Problem Problem 120 13 Irregular Colorings....... 13.1 Irregular Chromatic Number............. 13.2 de Bruijn Sequences and Digraphs.... 128 13.3 The Irregular Chromatic Numbers of Cycles... 130 134 Nordhaus-Gaddum Inegualities.... 133 14 Recognizable Colorings 137 141 The Rec 137 143 of Graph Complete ra 14.3 Graphs with Prescribed Order and Recognition Number........... 14.4 Recognizable Colorings of Cycles and Paths ...................... 14.5 Recognizable Colorings of Trees....................... 147 References 151 Index 155

x Contents 7.2 The Set Chromatic Numbers of Some Classes of Graphs .......... 69 7.3 Lower Bounds for the Set Chromatic Number...................... 71 8 Multiset Colorings .......................................................... 75 8.1 Multiset Chromatic Number ......................................... 75 8.2 Complete Multipartite Graphs ....................................... 77 8.3 Graphs with Prescribed Order and Multiset Chromatic Number .. 79 8.4 Multiset Colorings Versus Set Colorings............................ 81 9 Metric Colorings............................................................ 85 9.1 Metric Chromatic Number ........................................... 85 9.2 Graphs with Prescribed Order and Metric Chromatic Number .... 86 9.3 Bounds for the Metric Chromatic Number of a Graph ............. 88 9.4 Metric Colorings Versus Other Colorings........................... 90 10 Sigma Colorings ............................................................ 95 10.1 Sigma Chromatic Number ........................................... 95 10.2 Sigma Colorings Versus Multiset Colorings ........................ 97 10.3 Sigma Value and Range .............................................. 98 10.4 Four Colorings Problems ............................................ 101 11 Modular Colorings ......................................................... 103 11.1 A Checkerboard Problem ............................................ 103 11.2 Modular Colorings ................................................... 105 11.3 A Lights Out Problem................................................ 110 11.4 Closed Modular Colorings........................................... 111 12 A Banquet Seating Problem ............................................... 117 12.1 Seating Students at a Circular Table................................. 117 12.2 Modeling the Seating Problem by a Graph Coloring Problem ..... 120 13 Irregular Colorings......................................................... 125 13.1 Irregular Chromatic Number......................................... 125 13.2 de Bruijn Sequences and Digraphs .................................. 128 13.3 The Irregular Chromatic Numbers of Cycles ....................... 130 13.4 Nordhaus-Gaddum Inequalities...................................... 133 14 Recognizable Colorings .................................................... 137 14.1 The Recognition Numbers of Graphs ............................... 137 14.2 Complete Multipartite Graphs ....................................... 140 14.3 Graphs with Prescribed Order and Recognition Number........... 143 14.4 Recognizable Colorings of Cycles and Paths ....................... 144 14.5 Recognizable Colorings of Trees .................................... 147 References......................................................................... 151 Index ............................................................................... 155

List of Figures Fig.1.1 An Eulerian digraph D........ 5 Fig.2.1 A strong 5-edge coloring of a graph G........................ 8 Fig.2.2 A graph of order 16 with strong chromatic index 4. Fig.2.3 Eight k-binomial graphs for=2.3....... 4 r binomial- olorable a 25 dproper 3-bim ustra able grap 3 3 Fg2.7 ing a step of the proof f of Theorem 2. Illustrating the coloring c in the proof o Theorem 2.3.1 for =4.................. 16 Fig.2.8 The structure of a(k+1)-regular k-binomial-colorable graph G of order 2-I in Theorem 2.3.3............ 年 Fg.3.1 A 6-regular 3-kaleidoscope G of order 8 Fig.3.2 Dlustrating a 10-kaleidos scopic coloring ofK in the m355 3 Fig.3.3 each of K7 and K F1g.3.4 An irregular factorization ={F1F2,F3}0f0..。... 42 Fig.3.5 An irregular factorization F2.F of Ku..................... Fig.3.6 The location of the vertices of the graph G6...................... Fig.3.7 The subgraph F2 for r=6 and r=8............................. Fig.3.8 The subgraphs F1.F2 and F:in G6 Fig.3.9 The triangular sets X for Gio and Gs Fig.3.10 sets X1 and X2 for Gs.... Fig.3.11 edges in Gs 32 Fig.4.1 Graceful colorings of Ka and C. 37 Fig.4.2 A graceful 5-coloring of 3... Fig.4.3 Graceful colorings of w6.W7.Ws............................ 41 Fig.4.4 A tree To with (To)=A(To)+3............................ Fig.4.5 A graph G withe(G=「

List of Figures Fig. 1.1 An Eulerian digraph D .............................................. 5 Fig. 2.1 A strong 5-edge coloring of a graph G ............................. 8 Fig. 2.2 A graph of order 16 with strong chromatic index 4................ 9 Fig. 2.3 Eight k-binomial graphs for k D 2; 3 ............................... 10 Fig. 2.4 Six proper binomial-colorable graphs .............................. 11 Fig. 2.5 A labeled proper 3-binomial-colorable graph ..................... 12 Fig. 2.6 Illustrating a step of the proof of Theorem 2.2.2................... 13 Fig. 2.7 Illustrating the coloring c in the proof of Theorem 2.3.1 for k D 4 ............................................ 16 Fig. 2.8 The structure of a .kC1/-regular k-binomial-colorable graph G of order 2k 1 in Theorem 2.3.3 ......................... 18 Fig. 3.1 A 6-regular 3-kaleidoscope G of order 8 ........................... 20 Fig. 3.2 Illustrating a 10-kaleidoscopic coloring of K13 in the proof of Theorem 3.2.2.............................................. 23 Fig. 3.3 A 3-kaleidoscopic coloring for each of K7 and K8 ................. 24 Fig. 3.4 An irregular factorization F D fF1; F2; F3g of K10 ............... 25 Fig. 3.5 An irregular factorization fF1; F2; F3g of K11 ...................... 27 Fig. 3.6 The location of the vertices of the graph G6 ....................... 28 Fig. 3.7 The subgraph F2 for r D 6 and r D 8 .............................. 29 Fig. 3.8 The subgraphs F1, F2 and F3 in G6 ................................. 30 Fig. 3.9 The triangular sets X` for G10 and G8 .............................. 30 Fig. 3.10 Edges in the two triangular sets X1 and X2 for G8 ................. 31 Fig. 3.11 Vertical and slanted edges in G8 .................................... 32 Fig. 4.1 Graceful colorings of K4 and C4 .................................... 37 Fig. 4.2 A graceful 5-coloring of Q3 ......................................... 38 Fig. 4.3 Graceful colorings of W6; W7; W8 .................................. 41 Fig. 4.4 A tree T0 with g.T0/ D .T0/ C 3 ................................ 46 Fig. 4.5 A graph G with g.G/ D ˙5ı 3 ..................................... 51 xi

xii List of Figures Fig.5.1 Harmonious and non-harmonious graphs Fig.5.2 Harmonious colorings of graphs. 56 Fig.5.3 Harmonious and non-harmonious graphs Fig.6.1 s of the regions of a map M.(a)M.(b) m 64 Fig.6.2 fthe regions of map M.M. b proper,(c)set,(d)metric,(e)multiset,(f)sum.................. 65 Fig.7.1 A set coloring of a graph..... Fig.7.2 A set 3-coloring of the Grotzsch graph. Fig.7.3 A graph G with x:(G)=1+log,@(G)] 3 Fig.8.1 A multiset 2-coloring of a 4-chromatic graph G. Fig.8.2 The graph H in Case 1 for a=1 and b =4 Fig.8.3 The 2 of the proof of Theorem.1 for a=3 and 二4。。。。。。。 83 Fig.9.1 A4-chromatic graph G with u()=3................. 86 Fig.9.2 A graph G with (G)=3 and (G)=4.......................... Fig.9.3 An 8-chromatic graph G with u(G)=1 [log,@(G)]=4. Fig.9.4 A graph G and a vertex v of G with u(G-v)=u(G)+deg v 9 Fig.9.5 Graphs in the proof of Theorem 9.4.2 for a.10) 92 82 -sigma coloring and a sigma coloring of a graph Fig. %9 Fig.11.1 A 5 x 7 checkerboard... Fig.11.2 A coin placement on the 5 x 7 checkerboard .................. 104 Fig.11.3 A bipartite graph G with mc(G)=3....... 105 Fig.11.4 Modular colorings of C for8≤n≤1i 107 Fig 115 A tree T with mc(T)=3 107 11.6 Lights Out Gar 110 11.7 A bipartite graph G with mc(G)=3. 12 Fig.12. Seating a freshman,a sophomore and a junior 118 Fig.12.2 Iwo seating arrangements of four students ...................... 118 Fig.12.3 Four seating arrangements of five students......................... 118 Fig. 12.4 Seating arrangements of six or more students 119 Fig.12.5 A seating arrangement of 18 students....... 119 Fig.12.6 A seating arrang ment of 36 students 120

xii List of Figures Fig. 5.1 Harmonious and non-harmonious graphs .......................... 54 Fig. 5.2 Harmonious colorings of graphs.................................... 56 Fig. 5.3 Harmonious and non-harmonious graphs .......................... 60 Fig. 6.1 Three colorings of the regions of a map M. (a) M, (b) proper, (c) set, (d) sum .............................................. 64 Fig. 6.2 Four colorings of the regions of a map M. (a) M, (b) proper, (c) set, (d) metric, (e) multiset, (f) sum .................... 65 Fig. 7.1 A set coloring of a graph ............................................ 68 Fig. 7.2 A set 3-coloring of the Grötzsch graph............................. 72 Fig. 7.3 A graph G with s.G/ D 1 C dlog2 !.G/e ........................ 73 Fig. 8.1 A multiset 2-coloring of a 4-chromatic graph G ................... 76 Fig. 8.2 The graph H in Case 1 for a D 1 and b D 4 ....................... 82 Fig. 8.3 The graph G in Case 2 of the proof of Theorem 8.4.1 for a D 3 and b D 4 ................................................. 83 Fig. 9.1 A 4-chromatic graph G with .G/ D 3 ............................ 86 Fig. 9.2 A graph G with .G/ D 3 and !.G/ D 4.......................... 88 Fig. 9.3 An 8-chromatic graph G with .G/ D 1 C dlog2 !.G/e D 4 .... 89 Fig. 9.4 A graph G and a vertex v of G with .G v/ D .G/ C deg v . 91 Fig. 9.5 Graphs in the proof of Theorem 9.4.2 for a 2 f7; 10g and b D 30 ........................................................... 92 Fig. 10.1 A non-sigma coloring and a sigma coloring of a graph ........... 96 Fig. 10.2 3-Colorings of K5.2/;3.3/ ............................................. 99 Fig. 11.1 A 5 7 checkerboard ............................................... 104 Fig. 11.2 A coin placement on the 5 7 checkerboard ...................... 104 Fig. 11.3 A bipartite graph G with mc.G/ D 3 ............................... 105 Fig. 11.4 Modular colorings of Cn for 8  n  11 ........................... 107 Fig. 11.5 A tree T with mc.T/ D 3 ........................................... 107 Fig. 11.6 Lights Out Game .................................................... 110 Fig. 11.7 A bipartite graph G with mc.G/ D 3 ............................... 112 Fig. 12.1 Seating a freshman, a sophomore and a junior..................... 118 Fig. 12.2 Two seating arrangements of four students ........................ 118 Fig. 12.3 Four seating arrangements of five students......................... 118 Fig. 12.4 Seating arrangements of six or more students ..................... 119 Fig. 12.5 A seating arrangement of 18 students .............................. 119 Fig. 12.6 A seating arrangement of 36 students .............................. 120

List of Figures Fg12.7 Fig A seating arrangement of 75 students.. 128 .12.9 12.10 Se ating arrangement Fig.13.1 An irregular 4-coloring of the Petersen graph P......... Fig.13.2 The graph F8… Fig.13.3 Irregular 3-colorings of C3.Cs and C......................... Fig.13.4 Irregular 4-colorings of C4.C6 and Cs 129 Fig.13.5 An irregular 3-coloring of Co 3.6 13 The de Bruijn digraph B(3.2) The de Bruijndi 131 8 he de Br igraph D 33 Fig13,10 An irregular 4-coloring of C24..................................... 133 Fig.14. A minimum recognizable coloring of the Petersen graph......... Fig.14.2 A minimum recognizable coloring of the 3-cube 140 Fig. 14.3 Recognizable3-colorings of cycles C,3≤n≤g】 144 Fig 14.4 A recog gnizable 3-coloring of Cis 145 Fig 145 Mini m colorings for Ps and P2 A minin e able 4-coloring of Pp =2 14. A tree T of order 34 with m()=3............... Fig.14.9 A tree T of order 70 with m(T)=4............................ 148

List of Figures xiii Fig. 12.7 A seating arrangement of 75 students .............................. 121 Fig. 12.8 A graph coloring..................................................... 121 Fig. 12.9 Color codes of vertices.............................................. 122 Fig. 12.10 Seating arrangements of 3, 5, 7, or 9 students ..................... 123 Fig. 13.1 An irregular 4-coloring of the Petersen graph P ................... 126 Fig. 13.2 The graph F8 ......................................................... 127 Fig. 13.3 Irregular 3-colorings of C3, C5 and C7 ............................. 128 Fig. 13.4 Irregular 4-colorings of C4, C6 and C8 ............................. 129 Fig. 13.5 An irregular 3-coloring of C9 ....................................... 129 Fig. 13.6 The de Bruijn digraph B.3; 2/ ...................................... 130 Fig. 13.7 The de Bruijn digraph B.2; 4/ ...................................... 131 Fig. 13.8 A subdigraph of the de Bruijn digraph B.3; 3/..................... 131 Fig. 13.9 An Eulerian subdigraph D0 of the digraph D of Fig. 13.8 ......... 132 Fig. 13.10 An irregular 4-coloring of C24 ...................................... 133 Fig. 14.1 A minimum recognizable coloring of the Petersen graph ......... 139 Fig. 14.2 A minimum recognizable coloring of the 3-cube .................. 140 Fig. 14.3 Recognizable 3-colorings of cycles Cn, 3  n  9 ................ 144 Fig. 14.4 A recognizable 3-coloring of C18 ................................... 145 Fig. 14.5 Minimum colorings for P8 and P20 ................................. 146 Fig. 14.6 A minimum recognizable 4-coloring of P40 ....................... 146 Fig. 14.7 A tree of order 12 with rn.T/ D 2 .................................. 148 Fig. 14.8 A tree T of order 34 with rn.T/ D 3 ............................... 148 Fig. 14.9 A tree T of order 70 with rn.T/ D 4 ............................... 148

Chapter 1 Introduction One of the major areas Of all these colorings.the most studied and most popular graph colorings are the vertex colorings.These colorings came about through coloring the regions of planar graphs,that is,through coloring the regions of maps.In this chapter.we review some fundamental concepts and results on vertex and edge colorings that will be encountered as we proceed.In addition,we review some facts concerning degrees of vertices in graphs.outdegre s and inde es of vertices sin digraphs as Euleria dis tic is mentioned that will b e encountered often.We refer to the book [15]for graph theory notation and terminology not described here. 1.1 Graph Colorings of whether the re every lored ith four or fe t every tw aving a be ary lin n are colore differently blem has a le ngthy and col orful history (see 75).While a solution to this problem would not be found until 1976,there were many attempts to solve it by many individuals during its 124-vear history.A famous incorrect (although interesting)argument was made by the British lawyer and mathematician Alfred Bray Kempe in 1879.Kempe observed that coloring the regions of maps so that"adjacent regions"are colored differently was the same problem as coloring rtain diagrams so that two points ined by a line are colore g the vertices of a planar graph so that adjacent vertices ar colored differently) The Author 2016 P.Zhang,A Kaleic

Chapter 1 Introduction One of the major areas within graph theory is that of colorings, namely region colorings of graphs embedded on surfaces, vertex colorings and edge colorings. Of all these colorings, the most studied and most popular graph colorings are the vertex colorings. These colorings came about through coloring the regions of planar graphs, that is, through coloring the regions of maps. In this chapter, we review some fundamental concepts and results on vertex and edge colorings that will be encountered as we proceed. In addition, we review some facts concerning degrees of vertices in graphs, outdegrees and indegrees of vertices in digraphs as well as Eulerian graphs and digraphs. Finally, a fundamental fact from discrete mathematics is mentioned that will be encountered often. We refer to the book [15] for graph theory notation and terminology not described here. 1.1 Graph Colorings It was 1852 when the young British scholar Francis Guthrie brought up the question of whether the regions of every map could be colored with four or fewer colors so that every two regions having a boundary line in common are colored differently. This Four Color Problem has a lengthy and colorful history (see [75]). While a solution to this problem would not be found until 1976, there were many attempts to solve it by many individuals during its 124-year history. A famous incorrect (although interesting) argument was made by the British lawyer and mathematician Alfred Bray Kempe in 1879. Kempe observed that coloring the regions of maps so that “adjacent regions” are colored differently was the same problem as coloring the points of certain diagrams so that two points joined by a line are colored differently (coloring the vertices of a planar graph so that adjacent vertices are colored differently). © The Author 2016 P. Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-30518-9_1 1