A lower bound on the order of the largest induced forest in planar graphs with high girth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2016

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

Résumé

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

Dates et versions

lirmm-01375448 , version 1 (03-10-2016)

Identifiants

Citer

François Dross, Mickaël Montassier, Alexandre Pinlou. A lower bound on the order of the largest induced forest in planar graphs with high girth. Discrete Applied Mathematics, 2016, 214, pp.99-107. ⟨10.1016/j.dam.2016.06.011⟩. ⟨lirmm-01375448⟩
92 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More