Affordable Access

Publisher Website

On the complexity of finding the chromatic number of a recursive graph II: the unbounded case

Annals of Pure and Applied Logic
Publication Date
DOI: 10.1016/0168-0072(89)90037-7
  • Computer Science


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.

There are no comments yet on this publication. Be the first to share your thoughts.