The reverse mathematics of Brooks' theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912808052981760 |
|---|---|
| author | Marcone, Alberto Osso, Gian Marco |
| author_facet | Marcone, Alberto Osso, Gian Marco |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04001 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The reverse mathematics of Brooks' theorem Marcone, Alberto Osso, Gian Marco Logic Combinatorics 03B30, 05C15 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$. |
| title | The reverse mathematics of Brooks' theorem |
| topic | Logic Combinatorics 03B30, 05C15 |
| url | https://arxiv.org/abs/2601.04001 |