THE REVERSE MATHEMATICS AND UNIFORM RELATIONSHIPS BETWEEN THEOREMS ON COLOURING OF PLANAR GRAPHS
The Journal of Symbolic Logic · 26.06.2026 · 1-41
DOI: 10.1017/jsl.2026.10227 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Journal of Symbolic Logic, online erschienen am 26.06.2026. Verfasst von HEER TERN KOH und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Reverse mathematics is primarily interested in what set existence axioms are necessary and sufficient in a proof of a theorem. Much work has been done in classifying graph coloring theorems, studying k -regular graphs, k -chromatic graphs, and forests. This article takes inspiration from an old paper by Bean and studies graph coloring theorems restricted to planar graphs. Schmerl showed that these coloring theorems are all equivalent to WKL ${{\mathtt {WKL}}}$ monospace upper W upper K upper L over RCA 0 ${\mathtt {RCA}_{0}}$ monospace upper R upper C upper A 0 . In this article, we utilise Weihrauch reducibility to provide a deeper analysis on the uniformity of these implications. Whilst the proofs provided by Schmerl are not obviously non-uniform, we show that in many instances, non-uniformity is indeed necessary.
Zitieren
APA
KOH, H. T., & NG, K. M. (2026). THE REVERSE MATHEMATICS AND UNIFORM RELATIONSHIPS BETWEEN THEOREMS ON COLOURING OF PLANAR GRAPHS. The Journal of Symbolic Logic, 1-41. https://doi.org/10.1017/jsl.2026.10227
Vancouver
KOH HT, NG KM. THE REVERSE MATHEMATICS AND UNIFORM RELATIONSHIPS BETWEEN THEOREMS ON COLOURING OF PLANAR GRAPHS. The Journal of Symbolic Logic. 2026:1-41. doi:10.1017/jsl.2026.10227
BibTeX
@article{KOH2026,
author = {KOH, HEER TERN and NG, KENG MENG},
title = {THE REVERSE MATHEMATICS AND UNIFORM RELATIONSHIPS BETWEEN THEOREMS ON COLOURING OF PLANAR GRAPHS},
journal = {The Journal of Symbolic Logic},
year = {2026},
pages = {1--41},
doi = {10.1017/jsl.2026.10227}
}
EUVIMED