Journal of Symbolic Logic 41 (2):469-480 (1976)
We are concerned here with recursive function theory analogs of certain problems in chromatic graph theory. The motivating question for our work is: Does there exist a recursive (countably infinite) planar graph with no recursive 4-coloring? We obtain the following results: There is a 3-colorable, recursive planar graph which, for all k, has no recursive k-coloring; every decidable graph of genus p ≥ 0 has a recursive 2(χ(p) - 1)-coloring, where χ(p) is the least number of colors which will suffice to color any graph of genus p; for every k ≥ 3 there is a k-colorable, decidable graph with no recursive k-coloring, and if k = 3 or if k = 4 and the 4-color conjecture fails the graph is planar; there are degree preserving correspondences between k-colorings of graphs and paths through special types of trees which yield information about the degrees of unsolvability of k-colorings of graphs
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
Recursive Coloration of Countable Graphs.Hans-Georg Carstens & Peter Päppinghaus - 1983 - Annals of Pure and Applied Logic 25 (1):19-45.
Graph Colorings and Recursively Bounded Π10-Classes.J. B. Remmel - 1986 - Annals of Pure and Applied Logic 32 (2):185-194.
On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (1):1-38.
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.
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.
Similar books and articles
Inductive Inference and Unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.
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
Isomorphisms and Nonisomorphisms of Graph Models.Harold Schellinx - 1991 - Journal of Symbolic Logic 56 (1):227-249.
On Some Putative Graph-Theoretic Counterexamples to the Principle of the Identity of Indiscernibles.Rafael De Clercq - 2012 - Synthese 187 (2):661-672.
Isomorphism and Equational Equivalence of Continuous Λ-Models.Rainer Kerth - 1998 - Studia Logica 61 (3):403-415.
Added to index2009-01-28
Total downloads205 ( #19,864 of 2,171,974 )
Recent downloads (6 months)1 ( #326,556 of 2,171,974 )
How can I increase my downloads?