کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5778176 | 1633431 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Ordinals and graph decompositions
ترجمه فارسی عنوان
اختلافات مرتبه و گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
چکیده انگلیسی
A result of Diestel says that every countable simplicial tree decomposition can be rearranged to have length at most Ï. We show that no such ordinal bound can be found for the lengths of non-tree decompositions. More generally, we show that for each ordinal Ï, there is a decomposable graph whose shortest simplicial decomposition has length exactly Ï. Adapting this argument, we show that the index set of decomposable computable graphs DECOMP is Î 11 hard by showing that WO is 1-reducible to DECOMP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 168, Issue 4, April 2017, Pages 824-839
Journal: Annals of Pure and Applied Logic - Volume 168, Issue 4, April 2017, Pages 824-839
نویسندگان
Stephen Flood,