کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4661591 1344846 2016 12 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
A-computable graphs
ترجمه فارسی عنوان
نمودارهای قابل محاسبه
کلمات کلیدی
نظریه محاسبات؛ مسیرهای اویلر؛ عدد رنگی؛ نمودار های بسیار قابل محاسبه
03D25; 03D28; 03D45; 03C57Computability theory; Euler paths; Chromatic number; Highly 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 ∅

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 167, Issue 3, March 2016, Pages 235–246
نویسندگان
, , ,