pith. sign in

arxiv: 1710.06282 · v3 · pith:PN75C5IRnew · submitted 2017-10-17 · 💻 cs.DM · math.CO

A tight ErdH{o}s-P\'osa function for wheel minors

classification 💻 cs.DM math.CO
keywords everygraphintegerminorthereverticeswheelbest
0
0 comments X
read the original 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$.

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.