On cycle packings and feedback vertex sets

Abstract

For a graph $G$, let $\mathbf{fvs}$ and $\mathbf{cp}$ denote the minimum size of a feedback vertex set in $G$ and the maximum size of a cycle packing in $G$, respectively. Kloks, Lee, and Liu conjectured that $\mathbf{fvs}(G)\le 2\,\mathbf{cp}(G)$ if $G$ is planar. They proved a weaker inequality, replacing $2$ by $5$. We improve this, replacing $5$ by $3$, and verifying the resulting inequality for graphs embedded in surfaces of nonnegative Euler characteristic. We also generalize to arbitrary surfaces. We show that, if a graph $G$ embeds in a surface of Euler characteristic $c\le 0$, then $\mathbf{fvs}(G)\le 3\,\mathbf{cp}(G) + 103(-c)$. Lastly, we consider what the best possible bound on $\mathbf{fvs}$ might be, and give some open problems.