Effective coloration

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)
DOI 10.2307/2272247
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 28,165
Through your library
References found in this work BETA

No references found.

Add more references

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 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.

View all 6 citations / Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

205 ( #19,864 of 2,171,974 )

Recent downloads (6 months)

1 ( #326,556 of 2,171,974 )

How can I increase my downloads?

My notes
Sign in to use this feature

There  are no threads in this forum
Nothing in this forum yet.

Other forums