Effective coloration
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) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesLeonard 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.
J. C. E. Dekker (1981). Twilight Graphs. Journal of Symbolic Logic 46 (3):539-571.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #274,830 of 549,087 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
