کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661591 | 1633444 | 2016 | 12 صفحه PDF | دانلود رایگان |
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 ∅
Journal: Annals of Pure and Applied Logic - Volume 167, Issue 3, March 2016, Pages 235–246