EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

THE REVERSE MATHEMATICS AND UNIFORM RELATIONSHIPS BETWEEN THEOREMS ON COLOURING OF PLANAR GRAPHS

HEER TERN KOH, KENG MENG NG

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →