pith. sign in

arxiv: 1504.01949 · v1 · pith:CLUXZ5LInew · submitted 2015-04-08 · 💻 cs.DM · math.CO

A lower bound on the order of the largest induced forest in planar graphs with high girth

classification 💻 cs.DM math.CO
keywords sizefeedbackfracgirthplanarvertexboundgraph
0
0 comments X
read the original abstract

We give here new upper bounds on the size of a smallest feedback vertex set in planar graphs with high girth. In particular, we prove that a planar graph with girth $g$ and size $m$ has a feedback vertex set of size at most $\frac{4m}{3g}$, improving the trivial bound of $\frac{2m}{g}$. We also prove that every $2$-connected graph with maximum degree $3$ and order $n$ has a feedback vertex set of size at most $\frac{n+2}{3}$.

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.