pith. machine review for the scientific record. sign in

arxiv: 1003.3915 · v1 · submitted 2010-03-20 · 🧮 math.CO

Recognition: unknown

The Erd\"os-P\'osa property for clique minors in highly connected graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords minorsconnectedconnectivityfunctionadditiveassumeboundclique
0
0 comments X
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.