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


Abstract This article has no associated abstract. (fix it)
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(89)90029-8
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,443
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Effective Coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Recursive Coloration of Countable Graphs.Hans-Georg Carstens & Peter Päppinghaus - 1983 - Annals of Pure and Applied Logic 25 (1):19-45.
Nondeterministic Bounded Query Reducibilities.Richard Beigel, William Gasarch & Jim Owings - 1989 - Annals of Pure and Applied Logic 41 (2):107-118.
A Cardinality Version of Biegel's Nonspeedup Theorem.James C. Owings - 1989 - Journal of Symbolic Logic 54 (3):761-767.

Add more references

Citations of this work BETA

Index Sets for Π01 Classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
Nondeterministic Bounded Query Reducibilities.Richard Beigel, William Gasarch & Jim Owings - 1989 - Annals of Pure and Applied Logic 41 (2):107-118.
On the Finiteness of the Recursive Chromatic Number.William I. Gasarch & Andrew C. Y. Lee - 1998 - Annals of Pure and Applied Logic 93 (1-3):73-81.

Add more citations

Similar books and articles

Effective Coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Measurable Chromatic Numbers.Benjamin D. Miller - 2008 - Journal of Symbolic Logic 73 (4):1139-1157.
Generic Graph Construction.James E. Baumgartner - 1984 - Journal of Symbolic Logic 49 (1):234-240.
Weak Borel Chromatic Numbers.Stefan Geschke - 2011 - Mathematical Logic Quarterly 57 (1):5-13.
On the Finiteness of the Recursive Chromatic Number.William I. Gasarch & Andrew C. Y. Lee - 1998 - Annals of Pure and Applied Logic 93 (1-3):73-81.
Wild Edge Colourings of Graphs.Mirna Džamonja, Péter Komjáth & Charles Morgan - 2004 - Journal of Symbolic Logic 69 (1):255 - 264.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups.Philip Scowcroft - 2007 - Notre Dame Journal of Formal Logic 48 (4):521-550.

Analytics

Added to PP index
2014-01-16

Total views
9 ( #831,023 of 2,292,073 )

Recent downloads (6 months)
1 ( #823,434 of 2,292,073 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature