Graph Coloring and Reverse Mathematics

Mathematical Logic Quarterly 46 (4):543-548 (2000)
  Copy   BIBTEX

Abstract

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL0 over RCA0 Every locally k-colorable graph is m-colorable

Categories

Keywords

Reprint years

DOI

10.1002/1521-3870(200010)46:4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Reverse Mathematics and Grundy colorings of graphs.James H. Schmerl - 2010 - Mathematical Logic Quarterly 56 (5):541-548.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
Strict reverse mathematics draft.Harvey M. Friedman - unknown
The Dirac delta function in two settings of Reverse Mathematics.Sam Sanders & Keita Yokoyama - 2012 - Archive for Mathematical Logic 51 (1-2):99-121.
Undecidable theories and reverse mathematics.James H. Schmerl - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001. pp. 21--349.
Questioning Constructive Reverse Mathematics.I. Loeb - 2012 - Constructivist Foundations 7 (2):131-140.
Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
Reverse mathematics and rank functions for directed graphs.Jeffry L. Hirst - 2000 - Archive for Mathematical Logic 39 (8):569-579.
Lebesgue Convergence Theorems and Reverse Mathematics.Xiaokang Yu - 1994 - Mathematical Logic Quarterly 40 (1):1-13.
Reverse mathematics of separably closed sets.Jeffry L. Hirst - 2006 - Archive for Mathematical Logic 45 (1):1-2.
Free sets and reverse mathematics.Carl G. Jockusch Jr - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001. pp. 104.
Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.

Analytics

Added to PP
2013-12-01

Downloads
16 (#880,136)

6 months
5 (#652,053)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

No references found.

Add more references