pith. sign in

arxiv: 1705.11133 · v1 · pith:AE2YVQSEnew · submitted 2017-05-31 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords forestfracinducedlinearorderplanartriangle-freevertices
0
0 comments X
read the original abstract

We prove that every triangle-free planar graph of order $n$ and size $m$ has an induced linear forest with at least $\frac{9n - 2m}{11}$ vertices, and thus at least $\frac{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 \frac{n}{2} \rceil + 1$.

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.