The reverse mathematics of Brooks' theorem

Abstract

This is an analysis of the status of Brooks' Theorem, a celebrated result in graph coloring, from the point of view of Reverse Mathematics. We prove that the restriction of Brooks' theorem to bounded graphs of degree greater than or equal to $3$ is provable in ${\mathsf{RCA}}_0$, while the statement for arbitrary graphs is equivalent to ${\mathsf{WKL}}_0$ over ${\mathsf{RCA}}_0$. Brooks' Theorem for degree $2$, even when restricted to bounded graphs, is equivalent to ${\mathsf{WKL}}_0$ over ${\mathsf{RCA}}_0$.

25 pages, 9 figures; minor changes following referee's comments