On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
From MaRDI portal
Publication:922525
DOI10.1016/0168-0072(89)90037-7zbMath0711.03013OpenAlexW4213194823MaRDI QIDQ922525
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)90037-7
Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15)
Related Items
The complexity of finding SUBSEQ\((A)\) ⋮ Nondeterministic bounded query reducibilities ⋮ Unbounded search and recursive graph problems ⋮ Binary search and recursive graph problems ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Index sets for \(\Pi^0_1\) classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive coloration of countable graphs
- An almost optimal algorithm for unbounded searching
- Terse, superterse, and verbose sets
- On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
- Searching, Merging, and Sorting in Parallel Computation
- Unbounded Searching Algorithms
- Effective coloration
- Recursive Colorings of Graphs
This page was built for publication: On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
