Feasible Graphs and Colorings

Mathematical Logic Quarterly 41 (3):327-352 (1995)
  Copy   BIBTEX


The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring



    Upload a copy of this work     Papers currently archived: 84,108

External links

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

Through your library

Similar books and articles

Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Graph Coloring and Reverse Mathematics.James H. Schmerl - 2000 - Mathematical Logic Quarterly 46 (4):543-548.
Reverse Mathematics and Grundy colorings of graphs.James H. Schmerl - 2010 - Mathematical Logic Quarterly 56 (5):541-548.
Partitions of large Rado graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
Twilight graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.
An empirical comparison of some approximate methods for graph coloring.Israel Rebollo-Ruiz & Manuel Graña - 2012 - In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. pp. 600--609.
Successors of singular cardinals and coloring theorems I.Todd Eisworth & Saharon Shelah - 2005 - Archive for Mathematical Logic 44 (5):597-618.
Potential continuity of colorings.Stefan Geschke - 2008 - Archive for Mathematical Logic 47 (6):567-578.
A high dimensional Open Coloring Axiom.Bin He - 2005 - Mathematical Logic Quarterly 51 (5):462-469.
Domatic partitions of computable graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2014 - Archive for Mathematical Logic 53 (1-2):137-155.


Added to PP

9 (#980,096)

6 months
2 (#334,016)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Feasible graphs with standard universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.

Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Polynomial-time abelian groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Polynomial-time versus recursive models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.

View all 6 references / Add more references