The Chromatic Number and Brooks' Theorem

Blicher, Helle

4. term

Mathematics, Master

2015

2015-06-07

37 pages

Dette speciale er skrevet ved Institut for Matematiske Fag, Aalborg Universitet og behandler begreber indenfor punktfarvning af grafer. Hvis man ønsker at punktfarve en graf, står man over for følgende optimeringsproblem: Hvad er det mindste antal farver, der er nødvendige for at kunne tildele en farve til hvert punkt, således at to nabopunkter ikke har samme farve? Dette mindste tal er kendt som det kromatiske tal og der gives en grundig gennemgang af egenskaber ved dette kromatiske tal for en graf G. Kromatisk grafteori kan dateres tilbage til 1850’erne, hvor Francis Guthrie opdagede det velkendte firfarveproblem: Kan ethvert landkort farves med højst fire farver, således at lande, der deler grænse, ikke har samme farve? Hovedvægten lægges på Brooks’ sætning i forskellige udgaver. Brooks beviste i 1941 uligheden mellem maksimumsgraden og det kromatiske tal for en graf G. Der redegøres naturligvis for det basale indenfor grafteori og for fundamentale underemner, såsom grådig farvning og kritiske grafer, og for sætninger, der er essentielle for at forstå og gennemføre de beviser, der har interesse i dette speciale. En gennemgang af en nyere version af Brooks’ sætning, udarbejdet af Chartrand og Zhang, viser, at på trods af stor diversitet i terminologi og formulering, er forskellen i den matematiske teknik minimal, da begge anvender veje, grådig farvning og permutation. I 1976 beviste Paul A. Catlin en sætning, der betragtes som en udvidelse af Brooks’ sætning. Catlins sætning siger, at hvis en graf G opfylder betingelserne i Brooks’ sætning, så indeholder G en monokromatisk, maksimal, uafhængig delmængde. For nyligt blev en forenet version af disse bevist og publiceret af Vaidy Sivaraman. Han anvender uafhængighed i grafer, matching og Halls betingelse for at gennemføre beviset. Hans bevis er dog utilskrækkeligt, forstået på den måde, at visse mellemregninger og forklaringer er udeladt. Derfor gives der i dette speciale en noget mere uddybende og detaljeret version af beviset.

This Master of Science Thesis reviews the concepts of vertex coloring and encompasses a thorough study of the chromatic number for a graph G. The main emphasis is on Brooks’ theorem in various editions. Brooks proved, in 1941, the inequality between a graph’s maximum degree and its chromatic number. The basic traits for graphs are accounted for, as well as fundamental subtopics and theorems essential for understanding and completing the proofs of interest. An examination of a more recent version of Brooks’ theorem by Chartrand and Zhang reveals that although terminology and phrasing is very diverse, the disparity in mathematical technique is minimal as both utilizes paths, greedy coloring, and permutation. In 1976 Catlin proved an extension to the theorem of Brooks and recently a unified version of these was published by Vaidy Sivaraman. He utilizes independence in graphs, matchings, and Hall’s condition in order to complete the proof. As the original unified proof seemed insufficient in the sense that the author left out some intermediate results and explanations, an elaborate version is presented here.

grafteori, kromatisk tal, farvning,, Brooks' sætning

Download
View record in AAU Student Projects