On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
We study the difficulty of computing the chromatic number (respectively, the recursive chromatic number) of a recursive graph, given a bound on that number. We show that a logarithmic number of queries to an oracle for the halting problem (respectively, the third level of the arithmetic hierarchy) are necessary and sufficient. These results are tight with respect to both parameters: number of queries and power of oracle.
scientific article; zbMATH DE number 4121984
scientific article