28210.6 Total Colorings of Graphs284Exercises for Chapter 1028911. Monochromatic and Rainbow Colorings28911.1 Ramsey Numbers29611.2 Turan's Theorem29911.3 Rainbow Ramsey Numbers11.4 Rainbow Numbers of Graphs30631411.5 Rainbow-Connected Graphs32011.6 The Road Coloring Problem324Exercises for Chapter 1132912. Complete Colorings32912.1 The Achromatic Number of a Graph33512.2 Graph Homomorphisms12.3 The Grundy Number of a Graph349356Exercises for Chapter 1235913. Distinguishing Colorings35913.1 Edge-Distinguishing Vertex Colorings37013.2 Vertex-Distinguishing Edge Colorings37913.3 Vertex-Distinguishing Vertex Colorings13.4 Neighbor-Distinguishing Edge Colorings385391Exercises for Chapter 1339714. Colorings, Distance, and Domination39714.1 T-Colorings14.2 L(2,1)-Colorings40314.3 Radio Colorings410-41714.4 Hamiltonian Colorings42514.5 Domination and Colorings43414.6EpilogueExercises for Chapter 14434加编锅5#Appendix: Study ProjectsGeneral ReferencesBibliographyIndex (Names and Mathematical Terms)List of Symbolsxi
10.6 Total Colorings of Graphs 282 Exercises for Chapter 10 284 11. Monochromatic and Rainbow Colorings 289 11.1 Ramsey Numbers 289 11.2 Tur´an’s Theorem 296 11.3 Rainbow Ramsey Numbers 299 11.4 Rainbow Numbers of Graphs 306 11.5 Rainbow-Connected Graphs 314 11.6 The Road Coloring Problem 320 Exercises for Chapter 11 324 12. Complete Colorings 329 12.1 The Achromatic Number of a Graph 329 12.2 Graph Homomorphisms 335 12.3 The Grundy Number of a Graph 349 Exercises for Chapter 12 356 13. Distinguishing Colorings 359 13.1 Edge-Distinguishing Vertex Colorings 359 13.2 Vertex-Distinguishing Edge Colorings 370 13.3 Vertex-Distinguishing Vertex Colorings 379 13.4 Neighbor-Distinguishing Edge Colorings 385 Exercises for Chapter 13 391 14. Colorings, Distance, and Domination 397 14.1 T-Colorings 397 14.2 L(2, 1)-Colorings 403 14.3 Radio Colorings 410 14.4 Hamiltonian Colorings 417 14.5 Domination and Colorings 425 14.6 Epilogue 434 Exercises for Chapter 14 434 Appendix: Study Projects 439 General References 446 Bibliography 453 Index (Names and Mathematical Terms) 465 List of Symbols 480 xi
Chapter 0The Origin of GraphColoringsIf the countries in a map of South America (see Figure 1) were to be colored in sucha way that every two countries with a common boundary are colored differently,then this map could be colored using only four colors. Is this true of every map?While it is not difficult to color a map of South America with four colors, it isnotpossibletocolorthisrnap with less than four colors. In fact, every two of Brazil,Argentina, Bolivia, and Paraguay are neighboring countries and so four colors arerequired to color only these fotafreIt is probably clear why we might want two countries coloreddifferentlyiftheyhaveaotheycan beeasilydistinguished asdifferent counboundarwbecear,owver,whywewoudthnkthatforcootriese map. It may notwould be enought the countries of every map. After all, we can probablyorenvisionacomplicatedmaphavinga largenumber of countrieswith somecountrieshaving several neighboring countries, so constructed that a great many colors mightpossibly be needed to color the entire map. Here we understand neighboring coun-tries to mean two countries with a boundary line in common,not simply a singlepoint in commoWhile this problem may seem nothing more than a curiosity, it is precisely thisproblem that would prove to intrigue somanyfor so long and whose attemptedsolutions would contribute so significantly to the development of the area of math.ematics known as Graph Theory and especially to the subiect of graph coloringsChromatic Graph Theory.This map coloring problem would eventually acquire aname that would become known throughout the mathematical world.The Four Color Problem Can the countries of every map be colored with fouror fewer colors so that every two countries with a common boundary are coloreddifferently?1
Chapter 0 The Origin of Graph Colorings If the countries in a map of South America (see Figure 1) were to be colored in such a way that every two countries with a common boundary are colored differently, then this map could be colored using only four colors. Is this true of every map? While it is not difficult to color a map of South America with four colors, it is not possible to color this map with less than four colors. In fact, every two of Brazil, Argentina, Bolivia, and Paraguay are neighboring countries and so four colors are required to color only these four countries. It is probably clear why we might want two countries colored differently if they have a common boundary – so they can be easily distinguished as different countries in the map. It may not be clear, however, why we would think that four colors would be enough to color the countries of every map. After all, we can probably envision a complicated map having a large number of countries with some countries having several neighboring countries, so constructed that a great many colors might possibly be needed to color the entire map. Here we understand neighboring countries to mean two countries with a boundary line in common, not simply a single point in common. While this problem may seem nothing more than a curiosity, it is precisely this problem that would prove to intrigue so many for so long and whose attempted solutions would contribute so significantly to the development of the area of mathematics known as Graph Theory and especially to the subject of graph colorings: Chromatic Graph Theory. This map coloring problem would eventually acquire a name that would become known throughout the mathematical world. The Four Color Problem Can the countries of every map be colored with four or fewer colors so that every two countries with a common boundary are colored differently? 1
CHAPTER 0.THE ORIGIN OFGRAPH COLORINGSenehGuBrazBoliviaaraguaPacific OceanAtlanticOcea Falkland IslancFigure I: Map of South AmericaMany of the concepts, theorems, and problems of Graph Theory lie in the shadows of the Four Color Problem. Indeed ...Graph Theory is an area of mathematics whose past is aluays presentSince the maps we consider can be real or imagined, we can think of maps beingdivided into more general regions, rather than countries, states, provinces, or someother geographic entities.So just how did the Four Color Problem begin? It turns out that this questionhas arather well-documented answer.On 23October 1852,a student,namelyFred-erick Guthrie (1833-1886).at University College London visited his mathematicsprofessor.the famous Augustus De Morgan (1806-1871).to describean apparentmathematical discovery of his older brother Francis.While coloring the counties ofa map ofEngland,Francis Guthrie (1831-1899)observed thathecould color them
2 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS .. .. .. .. .. .. .. . ..... .... ..... ... . . . ........ ...... ....... ...... ....... ...... ....... ....... ...... ....... . ... ... ... ..................... . . .. . .... .... ..... .... .... ..... .... .... ..... .... .... .. .. .. .................. ....... ... ... ... ... ...... .... ..... ................. ... ... .. ........... .......... ............................... ................................................ ................................. ................................ . . . . . . . . . . . . .. .. . . ... ... ................ ...... ...... ... ... ... ........ ................... .. .................... .. ......... . . . .. . . ....... .... ... . ...... .............. .......... ....... ................................ . .... . .. . ..... .. .. .. .. .. . .. . ..... . . .............................. ........................ ............................ ......................................................... . .. . ... ......... ... ... .. . . .................................. . . .................... .................... .............. ............................................... .. . ................. .. . ........................ ............................................................................................................ . ... .. .. .. .. .. .. .. .. ... ... ... .. ... .............. ............. . . ..... . ... ... ... ... ........ .... .. .... ... .... .................... ...... ... ... .. .. .... ... ... ........ ...... . ............ ... .. . ............ ... . ..... ... ... ..... ... . .......................... ................... ................................ . .................................................. .................................... ......................................................... .. .. ... ... .. .. ................................... ... . ..... .. .. .. ... .. .. ..... .......... . .. ................. .. ... ................................... .................... ............................................ . ................... .................... .................................................................. ... ... .... ... . ...................................... ....... ......... ... .. ... .. ... .... ......... .. ... .... .... ...... ... ..... .... ..... .. . . .......... ......... .. ... .... ..... ........ .... ... .. ..... .. ... .... ............................................ ........... .. .. .. ... .. .. ... .... ... .. ... .... ..... ... ... .. ... .. .. .. ... ...... ....... . ...................... .. .... .. . . ... . .. ... ...... .. .. . .. ... ... .. ....... .. .. . .. . . . . .... . .. . .. ..... . .. .. . ... .... .. .. ... .... .. ....... ............ ... ... ... .... ... .. .. .... .. .. . .. ... ... . .. . .. . . . ... .. ... ... ... .. .......... .... . . . .. .. . ... . .. ... . .... ............................ . .. . ..................... ........................... .. ............. ................................ ............... . ... . ....................................................... ........ .... ... ...... ......... ... .... ... ... ........ ... ............ ........ .... .... ... .. ... .. ... .. . .. . .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .... ............... ......................................... . ... ... ... .. .. ... ........ .................................................................. ... ... ... .. .. ... .. .. .. . ......................................... . ... .. ... .. ....................... .. .... .... ..... ...... ....... ............................. .. ... . ..... ..... ... ........ ................. ... ... . ... . ... .. . .... ............... ........... ........................................... ............................................................. ................ .... ... ... ... .... ....... .... ..... .. ... ... .. .. .. .. ... ... .. ...... .. .... ........ . ................ ................................... .............. .................................................................................................... ............................................................. .. ................................................................................. ..................................................... .. . ............................................... ..................................... .................... .................. . ... .. ... ... ............................ ....... ....... ...... ...... ...... ....... .... .... ... ... .... .. ... ... ... .. ............................. ................................ ............................................................................................................. ........... . . .. .. .. .. .. ... .. . Venezuela Uruguay Falkland Islands Colombia Bolivia Chile Atlantic Ocean Brazil French Guiana Guyana Suriname Ecuador Peru Pacific Ocean Argentina Paraguay Figure 1: Map of South America Many of the concepts, theorems, and problems of Graph Theory lie in the shadows of the Four Color Problem. Indeed . . . Graph Theory is an area of mathematics whose past is always present. Since the maps we consider can be real or imagined, we can think of maps being divided into more general regions, rather than countries, states, provinces, or some other geographic entities. So just how did the Four Color Problem begin? It turns out that this question has a rather well-documented answer. On 23 October 1852, a student, namely Frederick Guthrie (1833–1886), at University College London visited his mathematics professor, the famous Augustus De Morgan (1806–1871), to describe an apparent mathematical discovery of his older brother Francis. While coloring the counties of a map of England, Francis Guthrie (1831–1899) observed that he could color them
3withfours,which led him to conjecturethat no more than four colors wouldrolobe needed to color the regions of any map.The Four Color Conjecture The regions of every map can be colored with fouor fewer colors in such a way that every two regions sharing a common boundaryare colored differently.Two years earlier, in 1850, Francis had earned a Bachelor of Arts degree fromUniversity College London and then a Bachelor of Laws degree in 1852.He wouldlaterbecomea mathematics professorhimself at the University of CapeTown inSouth Africa.Francis developed a lifelong interest in botanyand his extensivecollection of flora from the Cape Peninsula would later be placed in the GuthrieHerbarium in the University of Cape Town Botany Department. Several rare speciesof floraarenamed forhimFrancis Guthrie attempted to prove the Four Color Conjecturd althoughhethought he may havebeen successful, hewasnotcompletely satisfied withhisproofFrancis discussed his discovery with Frederick. With Francis' approval, Frederickmentioned the statement ofhisapparenttheoremtoProfessorr De Morgan, whoexpressed pleasure with it and believed it to be a new result. Evidently Frederickasked Professor De Morgan if he was aware of an argument that would establishthe truth of the theorem.This led De Morgan to write a letter to his friend, the famous Irish mathematician Sir William Rowan Hamilton (1805-1865) in Dublin. These two mathematicalgiants had corresponded for years, although apparently had met only once. De Morgan wrote (in part):My dear Hamilton:A student of mine asked me to day to give him a reason for a factwhich I did not know was a fact-and do not yet.He says that if afigure be any how divided and the compartments differently coloured sothat figures with any portion of common boundary lines are differentlycoloured - four colours may be wanted but not more - the following ishis case in which four are wanted.ABCD arenames ofcoloursQuery cannot a necessity for five or more be invented ...My pupil says he guessed it colouring a map of England ..Themore I think of it the more evident it seems. If you retort with sovery simple case which makes me out a stupid animal, I think I must doas the Sphynr did
3 with four colors, which led him to conjecture that no more than four colors would be needed to color the regions of any map. The Four Color Conjecture The regions of every map can be colored with four or fewer colors in such a way that every two regions sharing a common boundary are colored differently. Two years earlier, in 1850, Francis had earned a Bachelor of Arts degree from University College London and then a Bachelor of Laws degree in 1852. He would later become a mathematics professor himself at the University of Cape Town in South Africa. Francis developed a lifelong interest in botany and his extensive collection of flora from the Cape Peninsula would later be placed in the Guthrie Herbarium in the University of Cape Town Botany Department. Several rare species of flora are named for him. Francis Guthrie attempted to prove the Four Color Conjecture and although he thought he may have been successful, he was not completely satisfied with his proof. Francis discussed his discovery with Frederick. With Francis’ approval, Frederick mentioned the statement of this apparent theorem to Professor De Morgan, who expressed pleasure with it and believed it to be a new result. Evidently Frederick asked Professor De Morgan if he was aware of an argument that would establish the truth of the theorem. This led De Morgan to write a letter to his friend, the famous Irish mathematician Sir William Rowan Hamilton (1805–1865) in Dublin. These two mathematical giants had corresponded for years, although apparently had met only once. De Morgan wrote (in part): My dear Hamilton: A student of mine asked me to day to give him a reason for a fact which I did not know was a fact – and do not yet. He says that if a figure be any how divided and the compartments differently coloured so that figures with any portion of common boundary lines are differently coloured – four colours may be wanted but not more – the following is his case in which four are wanted. .. ... .... ...... ....... .............. ............. ......... ........ ..... .... ... ... . .. ... ... .... .... ....... ........ .............. ................ .......... ... ........ ....... ..... .... ... .. .... A B C A B C D are D names of colours Query cannot a necessity for five or more be invented . . . My pupil says he guessed it colouring a map of England . . .. The more I think of it the more evident it seems. If you retort with some very simple case which makes me out a stupid animal, I think I must do as the Sphynx did . .
CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSIn De Morgan's lettertoHamilton, he refersto the"Sphynx"(or Sphinx).Whilethe Sphinx is a male statue of a lion with the head of a human in ancient Egyptwhich guards the entrance to a temple, the Greek Sphinx is a female creature ofbad luck who sat atop a rock posing the following riddle to all those who pass by:What animal is that which in the morning goes on four fet, at noon ontwo, and in the evening upon three?Thoswho did not solve the riddle were killed. Only Oedipus (the titcharactein Oedipus Rer by Sophocles, a play about how people do not control their owndestiny) answered the riddle corectly as"Man'whoin childhood (the morning oflife) creeps on hands and knees, in manhood (thenoon of life) walks upright, andin old age (the evening of life) walks with the aid of a cane. Upon learning that herriddle had been solved, the Sphinx cast herself from the rock and perished, a fateDe Morgan had envisioned for himselfifhis riddle (the Four Color Problem) hadan easy and immediate solution.In De Morgan's letter to Hamilton, De Morgan attempted to explain why theproblem appeared to be difficult. He followed this explanation by writing:But it is tricky work and I am not sure of all convolutions-What doyou say? And has it, if true been noticed?Among Hamilton's numerousmathematical accomplishments was his remarkable work with quaternions.Hamilton's quaternions are a 4-dimensional svstem ofnumbers of the form a + bi + cj + dk, where a,b,c, d e R and ,? = j2-2-When c- 0.these numbers are the 2-dimensional system of complex nunberswhile when b= d - 0, these numbers are simply real numbers. Although it isnonplace for binary operations in algebraic structures to be commutative, suchis not the case for products of quaternions. For example, i. j = k but j -i - -h.Since De Morgan had shown an interest in Hamilton's research on quaternions aswell asother subjects Hamilton had studied itislikely that De Morgan expectedI enthusiastic reply to his letter to Hamilton.Such was not the case, however.Indeed, on 26 October 1852, Hamilton gave a quick but unexpected response:I am not likely to attempt your “quaternion" of colours very soon.Hamilton's response did nothing however to diminish De Morgan's interest in theFourColorProbleSince De Morgan's letter to Hamilton did not mention Frederick Guthrie byname, there may bereason to question whether Frederick was in fact the studento whom De Morgan was referring and that it was Frederick's older brother Franciswhowasthe originatorof theFour Color ProblemIn 1852Frederick Guthrie was a teenager.He would go on to become a distinguished physics professor and founder of the Physical Society in Londor.Anareathat he studied is the scienceof thermionic emission-firstreported byFrederickGuthrie in 1873. He discovered that a red-hot iron sphere with a positive charge
4 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS In De Morgan’s letter to Hamilton, he refers to the “Sphynx” (or Sphinx). While the Sphinx is a male statue of a lion with the head of a human in ancient Egypt which guards the entrance to a temple, the Greek Sphinx is a female creature of bad luck who sat atop a rock posing the following riddle to all those who pass by: What animal is that which in the morning goes on four feet, at noon on two, and in the evening upon three? Those who did not solve the riddle were killed. Only Oedipus (the title character in Oedipus Rex by Sophocles, a play about how people do not control their own destiny) answered the riddle correctly as “Man”, who in childhood (the morning of life) creeps on hands and knees, in manhood (the noon of life) walks upright, and in old age (the evening of life) walks with the aid of a cane. Upon learning that her riddle had been solved, the Sphinx cast herself from the rock and perished, a fate De Morgan had envisioned for himself if his riddle (the Four Color Problem) had an easy and immediate solution. In De Morgan’s letter to Hamilton, De Morgan attempted to explain why the problem appeared to be difficult. He followed this explanation by writing: But it is tricky work and I am not sure of all convolutions – What do you say? And has it, if true been noticed? Among Hamilton’s numerous mathematical accomplishments was his remarkable work with quaternions. Hamilton’s quaternions are a 4-dimensional system of numbers of the form a + bi + cj + dk, where a, b, c, d ∈ R and i 2 = j 2 = k 2 = −1. When c = d = 0, these numbers are the 2-dimensional system of complex numbers; while when b = c = d = 0, these numbers are simply real numbers. Although it is commonplace for binary operations in algebraic structures to be commutative, such is not the case for products of quaternions. For example, i · j = k but j · i = −k. Since De Morgan had shown an interest in Hamilton’s research on quaternions as well as other subjects Hamilton had studied, it is likely that De Morgan expected an enthusiastic reply to his letter to Hamilton. Such was not the case, however. Indeed, on 26 October 1852, Hamilton gave a quick but unexpected response: I am not likely to attempt your “quaternion” of colours very soon. Hamilton’s response did nothing however to diminish De Morgan’s interest in the Four Color Problem. Since De Morgan’s letter to Hamilton did not mention Frederick Guthrie by name, there may be reason to question whether Frederick was in fact the student to whom De Morgan was referring and that it was Frederick’s older brother Francis who was the originator of the Four Color Problem. In 1852 Frederick Guthrie was a teenager. He would go on to become a distinguished physics professor and founder of the Physical Society in London. An area that he studied is the science of thermionic emission – first reported by Frederick Guthrie in 1873. He discovered that a red-hot iron sphere with a positive charge