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 foll
owing property: one can recursively determine the neighbors of a verte
x. Both of these have been studied in the literature. We consider an i
ntermediary notion: Let A be a set. An A-recursive graph is a recursiv
e 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 n
ot recursive, then there exists A-recursive graphs that are 2-colorabl
e but not recursively k-colorable for any k. This is false for highly-
recursive graphs but true for recursive graphs. Hence A-recursive grap
hs are closer in spirit to recursive graphs than to highly recursive g
raphs. (C) 1998 Elsevier Science B.V. All rights reserved.