The Chromatic Number and Brooks' Theorem
Translated title
Det kromatiske tal og Brooks' sætning
Author
Blicher, Helle
Term
4. term
Education
Publication year
2015
Submitted on
2015-06-05
Pages
37
Abstract
Dette speciale undersøger, hvordan man farver en grafs toppe, så forbundne toppe får forskellige farver (topfarvning), og giver en grundig gennemgang af det kromatiske tal (det mindste antal farver, der er nødvendigt). Hovedfokus er Brooks' sætning fra 1941, som opstiller en ulighed mellem en grafs maksimale grad (det største antal kanter ved en enkelt top) og dens kromatiske tal. Specialet gennemgår de grundlæggende begreber i grafteori og de centrale delresultater og sætninger, der skal til for at forstå og gennemføre de relevante beviser. En analyse af en nyere version af Brooks' sætning af Chartrand og Zhang viser, at selv om terminologi og formulering varierer meget, er den matematiske teknik stort set den samme: argumenter med stier, grådig farvning (farvning af toppe én for én med den lavest mulige farve) og permutationer (omrækkefølge af toppe). Desuden behandles Catlins udvidelse fra 1976 og en nylig samlet version af disse resultater af Vaidy Sivaraman, hvis bevis bruger uafhængige mængder (sæt af toppe uden indbyrdes kanter), matchninger (kanter der ikke deler toppe) og Halls betingelse (et klassisk kriterium for matchninger). Da den offentliggjorte samlede bevisførelse udelader nogle mellemregninger og forklaringer, giver specialet her en mere udførlig, trinvis fremstilling.
This thesis studies how to color the vertices of a graph so that connected vertices get different colors (vertex coloring) and provides a thorough account of the chromatic number (the smallest number of colors needed). The main focus is Brooks' 1941 theorem, which states an inequality between a graph's maximum degree (the largest number of edges meeting one vertex) and its chromatic number. The thesis reviews core graph concepts and the background lemmas and theorems needed to understand and complete the proofs. It examines a modern version by Chartrand and Zhang, finding that although terminology and phrasing differ widely, the mathematical techniques are much the same: reasoning with paths, greedy coloring (coloring vertices one by one with the lowest available color), and permutations (reordering vertices). It also discusses Catlin's 1976 extension and a recent unified version by Vaidy Sivaraman, whose proof uses independent sets (vertices with no edges between them), matchings (disjoint edges), and Hall's condition (a classical criterion for matchings). Because the published unified proof omits some intermediate steps and explanations, the thesis presents a more detailed, step-by-step version.
[This abstract was generated with the help of AI]
Documents