Brooks' Theorem from the Alon--Tarsi Theorem
Stephen Hartke, UNL
Meeting Time: March 29, 2011, 2:00-2:50pm
Abstract:
Brooks' Theorem states that the chromatic number of a graph is bounded by its
maximum degree, except for complete graphs and odd cycles. Recently, Hladky,
Kral, and Schauz gave a proof of Brooks' Theorem using the Alon--Tarsi
Theorem, a powerful theorem that gives coloring results from the Combinatorial
Nullstellensatz. We will discuss the Alon--Tarsi Theorem, and present Hladky,
Kral, and Schauz's proof of Brooks' Theorem.