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.