Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems

Alex Crane, Carl Feghali, Felicia Lucke, Blair D. Sullivan, Madelyn J. Warr

arXivarxiv/2610.14374Oct 9, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.14374
curl -X POST /api/v1/records/arxiv/2610.14374/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.14374/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'