A lower bound on the order of the largest induced linear forest in triangle-free planar graphs

2017/05/31 by Dross, François, Montassier, Mickael, Pinlou, Alexandre · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1705.11133

Abstract

We prove that every triangle-free planar graph of order n and size m has an induced linear forest with at least (9n - 2m)/(11) vertices, and thus at least (5n + 8)/(11) vertices. Furthermore, we show that there are triangle-free planar graphs on n vertices whose largest induced linear forest has order \lceil (n)/(2) \rceil + 1.

Cited by

• Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets

Related

• A better bound on the largest induced forests in triangle-free planar graphs
• Large induced forests in planar graphs with girth 4 or 5
• Partitioning triangle-free planar graphs into a forest and a linear forest
• The maximum number of triangles in graphs without large linear forests
• Large induced subgraph with a given pathwidth in outerplanar graphs