On the complexity of finding the chromatic number of a recursive graph. I: The bounded case (Q1825865)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the complexity of finding the chromatic number of a recursive graph. I: The bounded case |
scientific article |
Statements
On the complexity of finding the chromatic number of a recursive graph. I: The bounded case (English)
0 references
1989
0 references
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.
0 references
oracle query
0 references
chromatic number
0 references
recursive graph
0 references
halting problem
0 references
arithmetic hierarchy
0 references
number of queries
0 references
power of oracle
0 references
0 references
0 references
