Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949942 | Discrete Applied Mathematics | 2016 | 9 Pages |
Abstract
We give here new lower bounds on the size of a largest induced forest in planar graphs with high girth. This is equivalent to upper bounds on the size of a smallest feedback vertex set. In particular, we prove that a planar graph with girth g and size m has a feedback vertex set of size at most 4m3g, improving the trivial bound of 2mg. We also prove that every 2-connected graph with maximum degree 3 and order n has a feedback vertex set of size at most n+23.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
François Dross, Mickael Montassier, Alexandre Pinlou,