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 \geq 0$ has a recursive $2(\chi(p) - 1)$-coloring, where $\chi(p)$ is the least number of colors which will suffice to color any graph of genus $p$; for every $k \geq 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.