Abstract A recursive graph is a graph whose edge set and vertex set are both recursive. Although the chromatic number of a recursive group 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 ƒ is a non-decreasing function such that ∑ i⩾02 −ƒ(i) is effectively computable, then there is an algorithm to determine χ( G) with ƒ(χ(G)) queries to K iff ∑ i⩾02 −ƒ(i)⩽1 (i.e., ƒ satisfies Kraft's inequality). We also investigate recursive chromatic numbers (which require queries to a set much harder than the halting set, namely ∅ M ), 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.