کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903621 1632748 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Polynomial expansion and sublinear separators
ترجمه فارسی عنوان
گسترش چندجمله ای و جداسازهای زیرین خطی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let C be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed 0<δ≤1, every n-vertex graph of C has a balanced separator of order O(n1−δ), then any depth-r minor (i.e. minor obtained by contracting disjoint subgraphs of radius at most r) of a graph in C has average degree O((rpolylogr)1∕δ). This confirms a conjecture of Dvořák and Norin.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 69, March 2018, Pages 49-53
نویسندگان
, ,