Excluded Forest Minors and the Erdős-Pósa Property

Details Excluded Forest Minors and the Erdős-Pósa Property Excluded Forest Minors and the Erdős-Pósa Property

2012-04-23

arxiv.org/abs/1204.5192v1

Mathematics

Combinatorics

Scientific paper

A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph $H$ as a minor has the so-called Erd\H{o}s-P\'osa property; namely, there exists a function $f$ depending only on $H$ such that, for every graph $G$ and every integer $k\in \N$, either $G$ has $k$ vertex-disjoint subgraphs each containing $H$ as a minor, or there exists a subset $X$ of vertices of $G$ with $|X| \leq f(k)$ such that $G - X$ has no $H$-minor. While the best function $f$ currently known is super-exponential in $k$, a $O(k \log k)$ bound is known in the special case where $H$ is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour, and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function $f$ can be taken to be linear when $H$ is a forest. This is best possible in the sense that no linear bound exists if $H$ has a cycle.

Affiliated with

Also associated with

No associations

Rating

Excluded Forest Minors and the Erdős-Pósa Property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Excluded Forest Minors and the Erdős-Pósa Property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Excluded Forest Minors and the Erdős-Pósa Property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518332