On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case

DOI10.1016/0168-0072(89)90037-7MaRDI QIDQ922525zbMATH 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)90037-7

zbMATH Keywords

chromatic numberrecursive graphunbounded search

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. I: The bounded case
• On the finiteness of the recursive chromatic number
• Unbounded search and recursive graph problems
• scientific article; zbMATH DE number 1303205
• Binary search and recursive graph problems

Cites work

• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• An almost optimal algorithm for unbounded searching
• Effective coloration
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• Recursive Colorings of Graphs
• Recursive coloration of countable graphs
• Searching, Merging, and Sorting in Parallel Computation
• Terse, superterse, and verbose sets
• Unbounded Searching Algorithms

Cited in

(9)

• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• scientific article; zbMATH DE number 3900785 (Why is no real title available?)
• Unbounded search and recursive graph problems
• \(A\)-computable graphs
• Nondeterministic bounded query reducibilities
• Binary search and recursive graph problems
• Index sets for \(\Pi^0_1\) classes
• The complexity of finding SUBSEQ\((A)\)
• Feasible Graphs and Colorings

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

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