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 ofviiPREFACE 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 be￾tween 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 dis￾tinguishing 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, student￾friendly 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 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