کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653348 | 1632766 | 2016 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sublinear separators, fragility and subexponential expansion
ترجمه فارسی عنوان
جداسازهای زیر خطی، شکنندگی و گسترش زیر عنصر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let GG be a subgraph-closed graph class with bounded maximum degree. We show that if GG has balanced separators whose size is smaller than linear by a polynomial factor, then GG has subexponential expansion. This gives a partial converse to a result of Nešetřil and Ossona de Mendez. As an intermediate step, the proof uses a new kind of graph decompositions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 52, Part A, February 2016, Pages 103–119
Journal: European Journal of Combinatorics - Volume 52, Part A, February 2016, Pages 103–119
نویسندگان
Zdeněk Dvořák,