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.