On the complexity of finding the chromatic number of a recursive graph. I: The bounded case (Q1825865)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:1825865 |
scientific article; zbMATH DE number 4121984
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the complexity of finding the chromatic number of a recursive graph. I: The bounded case |
scientific article; zbMATH DE number 4121984 |
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
0.942096471786499
0 references
0.8477984666824341
0 references
0.7855404019355774
0 references
0.7802212834358215
0 references
