Large induced forests in planar graphs with girth 4 or 5
Preprint
Abstract
We give here some new lower bounds on the order of a largest induced forest in planar graphs with girth $4$ and $5$. In particular we prove that a triangle-free planar graph of order $n$ admits an induced forest of order at least $\frac{6n+7}{11}$ , improving the lower bound of Salavatipour [M. R. Salavatipour, Large induced forests in triangle-free planar graphs, Graphs and Combinatorics, 22:113-126, 2006]. We also prove that a planar graph of order $n$ and girth at least $5$ admits an induced forest of order at least $\frac{44n+50}{69}$.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- An improved bound on the largest induced forests for triangle-free planar graphsDiscrete Mathematics & Theoretical Computer Science, 2010
- Large Induced Forests in Triangle-Free Planar GraphsGraphs and Combinatorics, 2006
- Problems and results in extremal combinatorics—IDiscrete Mathematics, 2003
- Minimum feedback vertex set and acyclic coloringInformation Processing Letters, 2002
- Large induced forests in sparse graphsJournal of Graph Theory, 2001
- Maximum induced forests of planar graphsGraphs and Combinatorics, 1987