کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657195 1343722 2012 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Erdős–Pósa property for clique minors in highly connected graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Erdős–Pósa property for clique minors in highly connected graphs
چکیده انگلیسی

We prove the existence of a function f:N2→N such that, for all p,k∈N, every (k(p−3)+14p+14)-connected graph either has k disjoint Kp-minors or contains a set of at most f(p,k) vertices whose deletion kills all its Kp-minors. For fixed p⩾5, the connectivity bound of about k(p−3) is smallest possible, up to an additive constant: if we assume less connectivity in terms of k, there will be no such function f.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 102, Issue 2, March 2012, Pages 454-469