DISCRETE MATHEMATICS AND ITS APPLICATIONSSeriesEditorKENNETHH.ROSENCHROMATICGRAPHTHEORYGARY CHARTRANDPING ZHANGCRC)CRCPressA CHAPMANALLBOOK
PREFACEBeginning with the origin of the Four Color Problem in 1852, the field of graphcolorings has developed into one of the most popular areas of graph theory. Thisbook imtroduces graph theory with a coloring theme.It explores connections between major topics in graph theory and graph colorings, including Ramsey numbersand domination, as well as such emerging topics as list colorings, rainbow colorings.distance colorings related to the Channel Assignment Problem, and vertex/edge distinguishing colorings.Discussions of a historical, applied, and algorithmic natureare included. Each chapter in the text contains many exercises of varying levels ofdifficulty. There is also an appendix containing suggestions for study projectsThe authorsare honored tohave been invited by CRCPress to writeatextbook.Withtheelous literaturethatexists ongralh coloringsandrathe dynamic naof the subiect.we weremmediatelyfacedwiththechallengeof determining which topics to includeand,perhaps even more importantly,whichoyre.There are several instances when the same concept has been.1diedbydifferent.aunors using different terminology and different notation. Wefore required to make a number of decisions regarding terminology andwerethernotation. While nearly all mathematicians working on graph colorings use positiveintegers asas colors, there are also some who use nonnegative integers. There areinstances when colorings and labelings have been used synonymously. For the mostpart, colorings have been used when the primary goal has been either to minimizethe number of colors or the largest color (equivalently, the span of colors)Wedecided that this book should be intended forone ormore of thefllwingpurposes:. a course in graph theory with an emphasis on graph colorings, where thiscourse could beeithera beginning course ingraphtheory orafollow-up courseto an elementary graph theory course.. a reading course on graph colorings..a seminar on graph colorings.asareference book for individuals interested in graph colorings.To accomplish this, it has been our goal to write this book in an engaging, studentfriendly style so that it contains carefully explained proofs and examples and con-tains many exercises of varying difficulty.This book consists of 15 chapters (Chapters 0-14). Chapter 0 provides somebackground on the origin of graph colorings - primarily giving a discussion of theFour Color Problem. For those readers who desire a more extensive discussion of thehistory and solution of the Four Color Problem, we recommend the interesting bookbyRobin Wilson,titled Four Colors Suffice:HowtheMap Problem Was Solved.publishedbyPrincetonUniversityPress in 2002To achieve the goal of having the book self-contained, Chapters 1-5 have beenwritten to contain many of the fundamentals of graph theory that lie outside ofvii
PREFACE Beginning with the origin of the Four Color Problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. This book introduces graph theory with a coloring theme. It explores connections between major topics in graph theory and graph colorings, including Ramsey numbers and domination, as well as such emerging topics as list colorings, rainbow colorings, distance colorings related to the Channel Assignment Problem, and vertex/edge distinguishing colorings. Discussions of a historical, applied, and algorithmic nature are included. Each chapter in the text contains many exercises of varying levels of difficulty. There is also an appendix containing suggestions for study projects. The authors are honored to have been invited by CRC Press to write a textbook on graph colorings. With the enormous literature that exists on graph colorings and the dynamic nature of the subject, we were immediately faced with the challenge of determining which topics to include and, perhaps even more importantly, which topics to exclude. There are several instances when the same concept has been studied by different authors using different terminology and different notation. We were therefore required to make a number of decisions regarding terminology and notation. While nearly all mathematicians working on graph colorings use positive integers as colors, there are also some who use nonnegative integers. There are instances when colorings and labelings have been used synonymously. For the most part, colorings have been used when the primary goal has been either to minimize the number of colors or the largest color (equivalently, the span of colors). We decided that this book should be intended for one or more of the following purposes: • a course in graph theory with an emphasis on graph colorings, where this course could be either a beginning course in graph theory or a follow-up course to an elementary graph theory course, • a reading course on graph colorings, • a seminar on graph colorings, • as a reference book for individuals interested in graph colorings. To accomplish this, it has been our goal to write this book in an engaging, studentfriendly style so that it contains carefully explained proofs and examples and contains many exercises of varying difficulty. This book consists of 15 chapters (Chapters 0-14). Chapter 0 provides some background on the origin of graph colorings – primarily giving a discussion of the Four Color Problem. For those readers who desire a more extensive discussion of the history and solution of the Four Color Problem, we recommend the interesting book by Robin Wilson, titled Four Colors Suffice: How the Map Problem Was Solved, published by Princeton University Press in 2002. To achieve the goal of having the book self-contained, Chapters 1-5 have been written to contain many of the fundamentals of graph theory that lie outside of vii
This includes basic termraph colorings.ninologyand results,andconntivity,Eulerian and Hamiltonian graphs,matchings and factorizations, and graph'embeddings.. The remainder of the book (Chapters 6-14) deal exclusively withgraph colorings. Chapters 6 and 7 provide an introduction to vertex colorings andbounds for the chromatic number. The emphasis of Chapter 8 is vertex coloringsof graphs embedded on surfaces. Chapter 9 discusses a variety of restricted vertex colorings, including list colorings. Chapter 10 introduces edge colorings, whileChapter Il discusses monochromatic and rainbow edge colorings, including an in-troduction to Ramsey numbers. Chapter 1l also provides a discussion of the RoadColoring Problem. The main emphasis of Chapter 12 is complete vertex coloringsIn Chapter 13, several distinguishing vertex and edge colorings are described.InChapter 14many distance-related vertex colorings are introduced, some inspired bythe Channel Assignment Problem, as well as a discussion of domination in terms ofvertex coloringThere is an Appendix listing fourteen topics for those who may be interested ine independent studtwo sectionsprsiunor:horninencesathe end of the book.The first of these, titled General References, contains a list ofreferences. both for Chapter 0 and of a general nature for all succeeding chaptersThe second suc section (Bibliography) primarily contains a list of publications towhich specific referencemade in the text. Finally, there is an Index of Namelisting individuals referred to in this book, an Index of Mathematical Terms, and aList of Symbols.There arey people we wish to thank.First, our thanks to mathematicians Ken Appel, Tiziana Calamoneri,Nicolaas de Bruijn, Ermelinda DeLaVinaStephnocke, Staszek Radzizowkidwad Scmichel,obinTomas,OlivTogni, and Avraham Trahtman for kindly providing us with information and com-cating with us on some topics. Thank you as well to our friends Shashi Kapoorn11and Al Polimeni for their interest and encouragement in this project. We especiallywant to thank Bob Stern, Executive Editor of CRC Press, Taylor & Francis Group,for his constant communication, encouragement, and interest and for suggestingthis writing project to us.Finally, we thank Marsha Pronin, Project Coordinator,Samantha White, Editorial Assistant, and Jim McGovern, Project Editor for theircooperationG.C.& P.Z.vii
graph colorings. This includes basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the book (Chapters 6-14) deal exclusively with graph colorings. Chapters 6 and 7 provide an introduction to vertex colorings and bounds for the chromatic number. The emphasis of Chapter 8 is vertex colorings of graphs embedded on surfaces. Chapter 9 discusses a variety of restricted vertex colorings, including list colorings. Chapter 10 introduces edge colorings, while Chapter 11 discusses monochromatic and rainbow edge colorings, including an introduction to Ramsey numbers. Chapter 11 also provides a discussion of the Road Coloring Problem. The main emphasis of Chapter 12 is complete vertex colorings. In Chapter 13, several distinguishing vertex and edge colorings are described. In Chapter 14 many distance-related vertex colorings are introduced, some inspired by the Channel Assignment Problem, as well as a discussion of domination in terms of vertex colorings. There is an Appendix listing fourteen topics for those who may be interested in pursuing some independent study. There are two sections containing references at the end of the book. The first of these, titled General References, contains a list of references, both for Chapter 0 and of a general nature for all succeeding chapters. The second such section (Bibliography) primarily contains a list of publications to which specific reference is made in the text. Finally, there is an Index of Names, listing individuals referred to in this book, an Index of Mathematical Terms, and a List of Symbols. There are many people we wish to thank. First, our thanks to mathematicians Ken Appel, Tiziana Calamoneri, Nicolaas de Bruijn, Ermelinda DeLaVi˜na, Stephen Locke, Staszek Radziszowski, Edward Schmeichel, Robin Thomas, Olivier Togni, and Avraham Trahtman for kindly providing us with information and communicating with us on some topics. Thank you as well to our friends Shashi Kapoor and Al Polimeni for their interest and encouragement in this project. We especially want to thank Bob Stern, Executive Editor of CRC Press, Taylor & Francis Group, for his constant communication, encouragement, and interest and for suggesting this writing project to us. Finally, we thank Marsha Pronin, Project Coordinator, Samantha White, Editorial Assistant, and Jim McGovern, Project Editor for their cooperation. G.C. & P.Z. viii
Table of Contents10. The Origin of Graph Colorings271. Introduction to Graphs271.1 Fundamental Terminology301.2 Connected Graphs331.3 Distance in Graphs371.4 Isomorphic Graphs391.5 Common Graphs and Graph Operations441.6 Multigraphs and Digraphs47Exercises for Chapter 1532. Trees and Connectivity532.1 Cut-vertices, Bridges, and Blocks562.2 Trees592.3 Connectivity and Edge-Connectivity632.4 Menger's Theorem67Exercises for Chapter 2713. Eulerian and Hamiltonian Graphs713.1 Eulerian Graphs763.2 de Brujn Digraphs793.3 Hamiltonian Graphs87Exercises for Chapter 3914. Matchings and Factorization 914.1 Matchings984.2 Independence in Graphs1004.3 Factors and Factorization106Exercises for Chapter 41095. Graph Embeddings1095.1 Planar Graphs and the Euler Identity1185.2 Hamiltonian Planar Graphsix
Table of Contents 0. The Origin of Graph Colorings 1 1. Introduction to Graphs 27 1.1 Fundamental Terminology 27 1.2 Connected Graphs 30 1.3 Distance in Graphs 33 1.4 Isomorphic Graphs 37 1.5 Common Graphs and Graph Operations 39 1.6 Multigraphs and Digraphs 44 Exercises for Chapter 1 47 2. Trees and Connectivity 53 2.1 Cut-vertices, Bridges, and Blocks 53 2.2 Trees 56 2.3 Connectivity and Edge-Connectivity 59 2.4 Menger’s Theorem 63 Exercises for Chapter 2 67 3. Eulerian and Hamiltonian Graphs 71 3.1 Eulerian Graphs 71 3.2 de Bruijn Digraphs 76 3.3 Hamiltonian Graphs 79 Exercises for Chapter 3 87 4. Matchings and Factorization 91 4.1 Matchings 91 4.2 Independence in Graphs 98 4.3 Factors and Factorization 100 Exercises for Chapter 4 106 5. Graph Embeddings 109 5.1 Planar Graphs and the Euler Identity 109 5.2 Hamiltonian Planar Graphs 118 ix
5.3 Planarity Versus Nonplanarity1201315.4 Embedding Graphs on Surfaces1395.5 The Graph Minor Theorem141Exercises for Chapter 51476. Introduction to Vertex Colorings1476.1 The Chromatic Number of a Graph1536.2 Applications of Colorings1606.3 Perfect GraphsExercises for Chapter 61707. Bounds for the Chromatic Number1757.1 Color-Critical Graphs1751797.2 Upper Bounds and Greedy Colorings1897.3 Upper Bounds and Oriented Graphs1957.4 The Chromatic Number of Cartesian Products200Exercises for Chapter 72058. Coloring Graphs on Surfaces2058.1 The Four Color Problem2088.2 The Conjectures of Hajos and Hadwiger2118.3 Chromatic Polynomials8.4 The Heawood Map-Coloring Problem217219Exercises for Chapter 82239. Restricted Vertex Colorings2239.1 Uniquely Colorable Graphs2309.2 List Colorings2409.3 Precoloring Extensions of GraphsExercises for Chapter 924524910. Edge Colorings of Graphs24910.1 The Chromatic Index and Vizing's Theorem25510.2 Class One and Class Two Graphs26210.3 Tait Colorings26910.4 Nowhere-Zero Flows27910.5 List Edge Coloringsx
5.3 Planarity Versus Nonplanarity 120 5.4 Embedding Graphs on Surfaces 131 5.5 The Graph Minor Theorem 139 Exercises for Chapter 5 141 6. Introduction to Vertex Colorings 147 6.1 The Chromatic Number of a Graph 147 6.2 Applications of Colorings 153 6.3 Perfect Graphs 160 Exercises for Chapter 6 170 7. Bounds for the Chromatic Number 175 7.1 Color-Critical Graphs 175 7.2 Upper Bounds and Greedy Colorings 179 7.3 Upper Bounds and Oriented Graphs 189 7.4 The Chromatic Number of Cartesian Products 195 Exercises for Chapter 7 200 8. Coloring Graphs on Surfaces 205 8.1 The Four Color Problem 205 8.2 The Conjectures of Haj´os and Hadwiger 208 8.3 Chromatic Polynomials 211 8.4 The Heawood Map-Coloring Problem 217 Exercises for Chapter 8 219 9. Restricted Vertex Colorings 223 9.1 Uniquely Colorable Graphs 223 9.2 List Colorings 230 9.3 Precoloring Extensions of Graphs 240 Exercises for Chapter 9 245 10. Edge Colorings of Graphs 249 10.1 The Chromatic Index and Vizing’s Theorem 249 10.2 Class One and Class Two Graphs 255 10.3 Tait Colorings 262 10.4 Nowhere-Zero Flows 269 10.5 List Edge Colorings 279 x