Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657195 | Journal of Combinatorial Theory, Series B | 2012 | 16 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics