{"id":"arxiv/2610.14374","url":"https://arxiv.org/abs/2610.14374","tags":["math.CO"],"score":0,"title":"Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems","domain":"math.CO","source":"arxiv","authors":["Alex Crane","Carl Feghali","Felicia Lucke","Blair D. Sullivan","Madelyn J. Warr"],"reviews":0,"subject":"math.CO","summary":"Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree $Δ\\geq 3$, then it admits a proper $Δ$-coloring. In this paper, we give a new proof of a much stronger result: every such graph admits exponentially many proper $Δ$-colorings. Exponential lower bounds have been obtained previously by applying the Combinatorial Nullstellensatz. In contrast, our proof is via a surprisingly simple and constructive analysis of a textbook greedy coloring algorithm. The entire argument is accessible to non-specialists. We extend our techniques…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}