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

&
Annals of Pure and Applied Logic 45 (1):1-38 (1989)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(89)90029-8

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On the complexity of finding the chromatic number of a recursive graph II: the unbounded case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (3):227-246.
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.
Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Upper bounds on complexity of Frege proofs with limited use of certain schemata.Pavel Naumov - 2006 - Archive for Mathematical Logic 45 (4):431-446.
Strongly representable atom structures of cylindric algebras.Robin Hirsch & Ian Hodkinson - 2009 - Journal of Symbolic Logic 74 (3):811-828.
Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
Correlations entre complexification et instabilite dans une formalisation du concept de complexite.F. Collot - 1995 - Acta Biotheoretica 43 (1-2):195-204.
The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups.Philip Scowcroft - 2007 - Notre Dame Journal of Formal Logic 48 (4):521-550.
Using d-separation to calculate zero partial correlations in linear models with correlated errors.Peter Spirtes, Thomas Richardson, Christopher Meek, Richard Scheines & Clark Glymour - unknown

Analytics

Added to PP
2014-01-16

Downloads
22 (#669,532)

6 months
10 (#219,185)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.
Infinite Versions of Some Problems from Finite Complexity Theory.Jeffry L. Hirst & Steffen Lempp - 1996 - Notre Dame Journal of Formal Logic 37 (4):545-553.

View all 6 citations / Add more citations

References found in this work

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