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

DOI10.1016/0168-0072(89)90029-8zbMath0685.03033OpenAlexW2067489791MaRDI QIDQ1825865

William I. Gasarch, Richard Beigel

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 problemarithmetic hierarchyrecursive graphnumber of queriesoracle querypower of oracle

Mathematics Subject Classification ID

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

Related Items (8)

Infinite versions of some problems from finite complexity theory ⋮ Unbounded search and recursive graph problems ⋮ Binary search and recursive graph problems ⋮ On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case ⋮ The Mapmaker's dilemma ⋮ Hamiltonian paths in infinite graphs ⋮ On the finiteness of the recursive chromatic number ⋮ Index sets for \(\Pi^0_1\) classes

Cites Work

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

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