On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case (Q922525): Difference between revisions

[For Part I see ibid. 45, No.1, 1-38 (1989; Zbl 0685.03033).] 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 \(\chi\) (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 \(\sum_{i\geq 0}2^{-f(i)}\) is effectively computable, then there is an algorithm to determine \(\chi\) (G) with f(\(\chi\) (G)) queries to K iff \(\sum_{i\geq 0}2^{-f(i)}\leq 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 \(\emptyset ''')\), 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 the neighbors of a given node recursively), though there are some interesting differences when queries to K are allowed for free in the computation of a recursive chromatic number.