Name
Abstract | ||
|---|---|---|
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 Erdos-Posa property; namely, there exists a function f depending only on H such that, for every graph G and every positive integer k, the graph G has k vertex-disjoint subgraphs each containing H as a minor, or there exists a subset X of vertices of G with vertical bar X vertical bar <= f(k) such that G - X has no H-minor (see Robertson and Seymour, J. Combin. Theory Ser. B 41 (1986) 92-114). While the best function f currently known is 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 is possible if H has a cycle. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/S0963548313000266 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 22 | 5 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Fiorini | 1 | 402 | 42.93 |
| Gwenaël Joret | 2 | 196 | 28.64 |
| David R. Wood | 3 | 1073 | 96.22 |