Recognition: unknown
The Erd\"os-P\'osa property for clique minors in highly connected graphs
classification
🧮 math.CO
keywords
minorsconnectedconnectivityfunctionadditiveassumeboundclique
read the original abstract
We prove the existence of a function f: N^2 -> N such that for all p,k in N every (k(p-3) + 14p+14) - connected graph either has k disjoint K_p minors or contains a set of at most f(p,k) vertices whose deletion kills all its K_p minors. For fixed p > 4, 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.