On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
type: Item
instance of: scholarly article
title: On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
zbMATH Open document ID: 0685.03033
DOI: 10.1016/0168-0072(89)90029-8
author: Richard Beigel
author: William Gasarch
published in: Annals of Pure and Applied Logic
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4121984
zbMATH Keywords: oracle query
zbMATH Keywords: chromatic number
zbMATH Keywords: recursive graph
zbMATH Keywords: halting problem
zbMATH Keywords: arithmetic hierarchy
zbMATH Keywords: number of queries
zbMATH Keywords: power of oracle
MaRDI profile type: Publication
full work available at URL: 0168-0072(89)90029-8
OpenAlex ID: W2067489791
cites work: Polynomial terse sets
cites work: Effective coloration
cites work: Recursive Euler and Hamilton Paths
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
cites work: Terse, superterse, and verbose sets
cites work: Bounded query classes and the difference hierarchy
cites work: Nondeterministic bounded query reducibilities
cites work: Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
cites work: Recursive coloration of countable graphs
cites work: Q4249726
cites work: An Effective Version of Dilworth's Theorem
cites work: Recursive Colorings of Highly Recursive Graphs
cites work: An Effective Version of Hall's Theorem
cites work: The complexity of optimization problems
cites work: Searching, Merging, and Sorting in Parallel Computation
cites work: Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
cites work: Effective Matchmaking and k-Chromatic Graphs
cites work: A cardinality version of Beigel's nonspeedup theorem
cites work: Q5573961
cites work: Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
cites work: The Effective Version of Brooks' Theorem
cites work: Recursive Colorings of Graphs
cites work: On Parallel Searching
cites work: Recursively enumerable sets and degrees
cites work: On Schmerl's effective version of Brooks' theorem
cites work: Q3766851
cites work: Q3703297
description: scientific article; zbMATH DE number 4121984