On the finiteness of the recursive chromatic number

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,385

External links

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

Through your library

Similar books and articles

Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
Graph Coloring and Reverse Mathematics.James H. Schmerl - 2000 - Mathematical Logic Quarterly 46 (4):543-548.
Some natural decision problems in automatic graphs.Dietrich Kuske & Markus Lohrey - 2010 - Journal of Symbolic Logic 75 (2):678-710.
Stability among r.e. quotient algebras.John Love - 1993 - Annals of Pure and Applied Logic 59 (1):55-63.
Twilight graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.

Analytics

Added to PP
2014-01-16

Downloads
47 (#333,921)

6 months
13 (#281,206)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

Add more citations

References found in this work

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