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

DOI10.1016/0168-0072(89)90029-8zbMATH Open0685.03033OpenAlexW2067489791MaRDI QIDQ1825865FDOQ1825865

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

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

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)

Cites Work

• The complexity of optimization problems
• Title not available (Why is that?)
• An Effective Version of Dilworth's Theorem
• On Parallel Searching
• Effective coloration
• Bounded queries to SAT and the Boolean hierarchy
• Recursively enumerable sets and degrees
• Recursive Colorings of Highly Recursive Graphs
• Recursive Euler and Hamilton Paths
• Recursive Colorings of Graphs
• Title not available (Why is that?)
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
• Recursive coloration of countable graphs
• Effective Matchmaking and k-Chromatic Graphs
• Searching, Merging, and Sorting in Parallel Computation
• Title not available (Why is that?)
• Terse, superterse, and verbose sets
• Polynomial terse sets
• Bounded query classes and the difference hierarchy
• A cardinality version of Beigel's nonspeedup theorem
• 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
• Title not available (Why is that?)
• Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines
• On Schmerl's effective version of Brooks' theorem
• The Effective Version of Brooks' Theorem
• Nondeterministic bounded query reducibilities
• An Effective Version of Hall's Theorem

Cited In (11)

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

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)