pith. sign in

arxiv: 1611.04546 · v2 · pith:QXJGGZSXnew · submitted 2016-11-14 · 🧮 math.CO

A better bound on the largest induced forests in triangle-free planar graphs

classification 🧮 math.CO
keywords fracboundplanartriangle-freeforestgraphinducedlargest
0
0 comments X
read the original abstract

It is well-known that there exists a triangle-free planar graph of $n$ verticess such that the largest induced forest has size at most $\frac{5n}{8}$. Salavatipour proved that there is a forest of size at least $\frac{5n}{9.41}$ in any triangle-free planar graph of $n$ vertices. Dross, Montassier and Pinlou improved Salavatipour's bound to $\frac{5n}{9.17}$. In this work, we further improve the bound to $\frac{5n}{9}$. Our technique is inspired by the recent ideas from Lukot'ka, Maz{\'a}k and Zhu.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.