کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653348 1632766 2016 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sublinear separators, fragility and subexponential expansion
ترجمه فارسی عنوان
جداسازهای زیر خطی، شکنندگی و گسترش زیر عنصر
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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
نویسندگان
,