Premium
Brooks' Theorem and Beyond
Author(s) -
Cranston Daniel W.,
Rabern Landon
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21847
Subject(s) - lemma (botany) , mathematical proof , mathematics , combinatorics , conjecture , graph coloring , greedy coloring , list coloring , brooks' theorem , fractional coloring , vertex (graph theory) , graph , discrete mathematics , complete coloring , chordal graph , 1 planar graph , graph power , line graph , ecology , geometry , poaceae , biology
We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon–Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin–Kostochka Conjecture and Reed's Conjecture.