Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems
Abstract
Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree Δ≥ 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 to provide quantitative lower bounds on the number of colorings in several more general settings, namely Δ-length list coloring, degree-length list coloring (degree-choosability), and degenerate partitioning. In the latter setting, one is asked to partition the vertices such that each partite set induces a subgraph of bounded degeneracy. In contrast to the other coloring variants considered, no clean Brooks-type characterization is possible, since it is known that for some combinations of parameters determining the existence of even one valid partition is NP-hard. We give a new reduction which significantly extends the parameter regime for which determining the existence of a valid partition is NP-hard. Finally, we give a new proof of the classic degree-choosability theorem, generalizing the techniques behind a recent proof of Brooks' Theorem.
Related
- Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
- Dolgopyat estimate for partially hyperbolic systems: limit theorems and exponential mixing
- Korovkin type theorems for operators acting on functions of polynomial and exponential growth on [0,∞)
- Limit theorems for random matrix products with a simple top Lyapunov exponent
- Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
BibTeX
@misc{crane2026greedy,
title = {{Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems}},
author = {Alex Crane and Carl Feghali and Felicia Lucke and Blair D. Sullivan and Madelyn J. Warr},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14374},
eprint = {2610.14374},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14374},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems
AU - Alex Crane
AU - Carl Feghali
AU - Felicia Lucke
AU - Blair D. Sullivan
AU - Madelyn J. Warr
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14374
UR - https://arxiv.org/abs/2610.14374
AB - Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree Δ≥ 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 to provide quantitative lower bounds on the number of colorings in several more general settings, namely Δ-length list coloring, degree-length list coloring (degree-choosability), and degenerate partitioning. In the latter setting, one is asked to partition the vertices such that each partite set induces a subgraph of bounded degeneracy. In contrast to the other coloring variants considered, no clean Brooks-type characterization is possible, since it is known that for some combinations of parameters determining the existence of even one valid partition is NP-hard. We give a new reduction which significantly extends the parameter regime for which determining the existence of a valid partition is NP-hard. Finally, we give a new proof of the classic degree-choosability theorem, generalizing the techniques behind a recent proof of Brooks' Theorem.
ER -