Annals of Pure and Applied Logic 93 (1-3):73-81 (1998)

Abstract
A recursive graph is a graph whose vertex and edge sets are recursive. A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the neighbors of a vertex. We show that, if A is r.e. and not recursive, then there exists A-recursive graphs that are 2-colorable but not recursively k-colorable for any k. This is false for highly-recursive graphs but true for recursive graphs. Hence A-recursive graphs are closer in spirit to recursive graphs than to highly recursive graphs
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(98)00054-2
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,979
Through your library

References found in this work BETA

Effective Coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Recursive Coloration of Countable Graphs.Hans-Georg Carstens & Peter Päppinghaus - 1983 - Annals of Pure and Applied Logic 25 (1):19-45.

Add more references

Citations of this work BETA

A -Computable Graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2016 - Annals of Pure and Applied Logic 167 (3):235-246.

Add more citations

Similar books and articles

Measurable Chromatic Numbers.Benjamin D. Miller - 2008 - Journal of Symbolic Logic 73 (4):1139-1157.
Effective Coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Generic Graph Construction.James E. Baumgartner - 1984 - Journal of Symbolic Logic 49 (1):234-240.
Weak Borel Chromatic Numbers.Stefan Geschke - 2011 - Mathematical Logic Quarterly 57 (1):5-13.
Recursive in a Generic Real.Juichi Shinoda & Theodore A. Slaman - 2000 - Journal of Symbolic Logic 65 (1):164-172.
A Note on Finiteness in the Predicative Foundations of Arithmetic.Fernando Ferreira - 1999 - Journal of Philosophical Logic 28 (2):165-174.
Finiteness Axioms on Fragments of Intuitionistic Set Theory.Riccardo Camerlo - 2007 - Notre Dame Journal of Formal Logic 48 (4):473-488.
Max and Min Limiters.James Owings, William Gasarch & Georgia Martin - 2002 - Archive for Mathematical Logic 41 (5):483-495.

Analytics

Added to PP index
2014-01-16

Total views
33 ( #345,404 of 2,505,145 )

Recent downloads (6 months)
6 ( #119,040 of 2,505,145 )

How can I increase my downloads?

Downloads

My notes