The Chromatic Number and Brooks' Theorem

Student thesis: Master thesis (including HD thesis)

  • Helle Blicher
4. term, Mathematics, Master (Master Programme)
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
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
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.
Publication date5 Jun 2015
Number of pages37
Publishing institutionDept. of Mathematical Sciences, Aalborg University
ID: 213768333