On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

DOI10.1016/0168-0072(89)90029-8MaRDI QIDQ1825865zbMATH OpenOpenAlexFDO

Authors Richard Beigel, William Gasarch

Publication date 1989

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(89)90029-8

zbMATH Keywords

chromatic numberhalting problemrecursive grapharithmetic hierarchynumber of queriesoracle querypower of oracle

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• On the finiteness of the recursive chromatic number
• scientific article; zbMATH DE number 1303205
• Unbounded search and recursive graph problems
• Feasible Graphs and Colorings

Cites work

• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 4024790 (Why is no real title available?)
• scientific article; zbMATH DE number 1303203 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A cardinality version of Beigel's nonspeedup theorem
• An Effective Version of Dilworth's Theorem
• An Effective Version of Hall's Theorem
• Bounded queries to SAT and the Boolean hierarchy
• Bounded query classes and the difference hierarchy
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
• Effective Matchmaking and k-Chromatic Graphs
• Effective coloration
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• Nondeterministic bounded query reducibilities
• On Parallel Searching
• On Schmerl's effective version of Brooks' theorem
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Polynomial terse sets
• Recursive Colorings of Graphs
• Recursive Colorings of Highly Recursive Graphs
• Recursive Euler and Hamilton Paths
• Recursive coloration of countable graphs
• Recursively enumerable sets and degrees
• Searching, Merging, and Sorting in Parallel Computation
• Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
• Terse, superterse, and verbose sets
• The Effective Version of Brooks' Theorem
• The complexity of optimization problems

Cited in

(11)

• scientific article; zbMATH DE number 3900785 (Why is no real title available?)
• Infinite versions of some problems from finite complexity theory
• Unbounded search and recursive graph problems
• \(A\)-computable graphs
• The Mapmaker's dilemma
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Binary search and recursive graph problems
• Index sets for \(\Pi^0_1\) classes
• Hamiltonian paths in infinite graphs
• On the finiteness of the recursive chromatic number
• Feasible Graphs and Colorings

This page was built for publication: On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825865)