On the finiteness of the recursive chromatic number (Q1295384)

An \(A\)-recursive graph is an infinite graph whose vertex and edge sets are recursive and such that the neighbors of any node can be determined recursively. It is shown that if \(A\) is r.e. and not recursive and if \(k\) is any integer, then there exists an \(A\)-recursive graph that is 2-colorable but that cannot be recursively colored with \(k\) colors. This result was previously known to hold for recursive graphs, that is, for graphs whose vertex and edge sets are recursive but with no effectiveness property for determining the neighbors of a node.