Journal of Symbolic Logic 41 (2):469-480 (1976)
|Abstract||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)|
|Through your library||Configure|
Similar books and articles
Leonard M. Adleman & M. Blum (1991). Inductive Inference and Unsolvability. Journal of Symbolic Logic 56 (3):891-900.
Rainer Kerth (1998). Isomorphism and Equational Equivalence of Continuous Λ-Models. Studia Logica 61 (3):403-415.
Rafael de Clercq (2012). On Some Putative Graph-Theoretic Counterexamples to the Principle of the Identity of Indiscernibles. Synthese 187 (2):661-672.
James E. Baumgartner (1984). Generic Graph Construction. Journal of Symbolic Logic 49 (1):234-240.
Dov M. Gabbay & Andrzej Szałas (forthcoming). Annotation Theories Over Finite Graphs. Studia Logica.
Harold Schellinx (1991). Isomorphisms and Nonisomorphisms of Graph Models. Journal of Symbolic Logic 56 (1):227-249.
Peter Spirtes, Thomas Richardson, Christopher Meek, Richard Scheines & Clark Glymour, Using D-Separation to Calculate Zero Partial Correlations in Linear Models with Correlated Errors.
J. C. E. Dekker (1981). Twilight Graphs. Journal of Symbolic Logic 46 (3):539-571.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads1 ( #274,830 of 549,087 )
Recent downloads (6 months)0
How can I increase my downloads?