Feasible Graphs and Colorings

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

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
Keywords Feasible  Graph coloring  Polynom time graph  Recursive graph  Polynom time coloring  II 10 class  Exponential time coloring
Categories (categorize this paper)
DOI 10.1002/malq.19950410305
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: 40,785
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

Polynomial-Time Versus Recursive Models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
Polynomial-Time Abelian Groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Graph Colorings and Recursively Bounded Π10-Classes.J. B. Remmel - 1986 - Annals of Pure and Applied Logic 32 (2):185-194.

View all 6 references / Add more references

Citations of this work BETA

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

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 index

Total views
6 ( #915,142 of 2,243,843 )

Recent downloads (6 months)
3 ( #623,720 of 2,243,843 )

How can I increase my downloads?


My notes

Sign in to use this feature