Logo image
Sign in
A lower bound on the order of the largest induced forest in planar graphs with high girth
Journal article   Open access   Peer reviewed

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

François Dross, Mickaël Montassier and Alexandre Pinlou
Discrete Applied Mathematics, Vol.214, pp.99-107
2016

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 in has a feedback vertex set of size at most 4m/3g, improving the trivial bound of 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 n+2/3
url
Find in HALView
url
https://doi.org/10.1016/j.dam.2016.06.011View
Published (Version of record) Open

Metrics

1 Record Views

Details

Logo image