Article ID Journal Published Year Pages File Type
4657195 Journal of Combinatorial Theory, Series B 2012 16 Pages PDF
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