Feedback Vertex Sets and Cycle Packings in Subcubic Planar Graphs

Abstract

For a graph $G$, let $\tau(G)$ denote the minimum size of a set of vertices intersecting every cycle in $G$. Let $\vu(G)$ denote the maximum size of a collection of vertex-disjoint cycles of $G$. Erd\"{o}s and P\'{o}sa~\cite{erdos65} showed that $\tau(G) = O(\vu \log \vu(G))$ for general graphs, and that the bound is tight. Kloks et al.~\cite{kloks} showed that for planar graphs $\tau(G) \leq 5\vu(G)$ and conjectured that $\tau(G) \leq 2\vu(G)$ for any planar graph $G$. The coefficient 5 has been improved to 3 independently in ~\cite{ma, chappell,chen}. However, the conjecture remains open even for subcubic graphs, which are graphs with maximum degree at most 3.

We show that for any planar subcubic graph $G$, $\tau(G) \leq \frac{5}{2}\vu(G)$. We also study the connectivity and girth of a vertex-minimal counterexample to the conjecture of Kloks et al. for subcubic graphs. In the end we present a list of reducible configurations, which are graphs $H$, such that if $G$ is a vertex-minimal counterexample to the conjecture of Kloks et al. for planar subcubic graphs, then $G$ cannot contain $H$ as a subgraph.