A-computable graphs

We consider locally finite graphs with vertex set NN. A graph G is computable if the edge set is computable and highly computable   if the neighborhood function NGNG (which given v   outputs all of its adjacent vertices) is computable. Let χ(G)χ(G) be the chromatic number of G   and χc(G)χc(G) be the computable chromatic number of G. Bean showed there is a computable graph G   with χ(G)=3χ(G)=3 and χc(G)=∞χc(G)=∞, but if G   is highly computable then χc(G)≤2χ(G)χc(G)≤2χ(G). In a computable graph the neighborhood function is Δ20. In highly computable graphs it is computable. It is natural to ask what happens between these extremes. A computable graph G is A-computable   if NG≤TANG≤TA. Gasarch and Lee showed that if A is c.e. and not computable then there exists an A-computable graph G   such that χ(G)=2χ(G)=2 but χc(G)=∞χc(G)=∞. Hence for A noncomputable and c.e., A  -computable graphs behave more like computable graphs than highly computable graphs. We prove analogous results for Euler paths and domatic partitions. Gasarch and Lee left open what happens for other Δ20 sets A  . We show that there exists an ∅