Back to Search
Start Over
A tight Erd\H{o}s-P\'osa function for wheel minors
- Source :
- SIAM J. Discrete Math. 32-3 (2018), pp. 2302-2312
- Publication Year :
- 2017
-
Abstract
- Let $W_t$ denote the wheel on $t+1$ vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k\geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.<br />Comment: 15 pages, 1 figure
- Subjects :
- Computer Science - Discrete Mathematics
Mathematics - Combinatorics
05C75
G.2.2
Subjects
Details
- Database :
- arXiv
- Journal :
- SIAM J. Discrete Math. 32-3 (2018), pp. 2302-2312
- Publication Type :
- Report
- Accession number :
- edsarx.1710.06282
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1137/17M1153169