Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems

Alex Crane, Carl Feghali, Felicia Lucke +2

Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree $\Delta \ge 3$, then it admits a proper $\Delta$-coloring. In this p…