ON THE FINITENESS OF THE RECURSIVE CHROMATIC NUMBER

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.