On the complexity of finding the chromatic number of a recursive graph II: the unbounded case
Richard Beigel, William I. Gasarch · Annals of Pure and Applied Logic · 1989
A recursive graph is a graph whose edge set and vertex set are both recursive. Although the chromatic number of a recursive graph G (denoted #(G)) cannot be determined recursively, it can be determined if queries to the halting set are allowed. We show that the problem of determining the chromatic number of a recursive graph with a minimum number of queries to the halting set, is closely related to the unbounded search problem. In particular if f is a non-decreasing function such that P i#0 2 -f(i) is effectively computable, then there is an algorithm to determine #(G) with f(#(G)) queries to K i# P i#0 2 -f(i) # 1 (i.e., f satisfies Kraft's inequality). We also investigate recursive chromatic numbers (which require queries to a set much harder than the halting set, namely # ### ), the effect of allowing queries to a weaker set, and the effect of being able to ask p queries at a time. Most of our results are also true for highly recursive graphs (graphs where one can determine t...