Large induced forests in planar graphs with girth 4 or 5

2014/09/04 by Dross, François, Montassier, Mickael, Pinlou, Alexandre · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1409.1348

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 (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 (44n+50)/(69).

Cited by

• A Note on Large Degenerate Induced Subgraphs in Sparse Graphs
• Large induced subgraph with a given pathwidth in outerplanar graphs

Related

• A better bound on the largest induced forests in triangle-free planar graphs
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• Large induced subgraph with a given pathwidth in outerplanar graphs
• Induced forests in regular graphs with large girth