New results on large induced forests in graphs

Abstract

For a graph $G$, let $a(G)$ denote the maximum size of a subset of vertices that induces a forest. We prove the following. 1. Let $G$ be a graph of order $n$, maximum degree $\Delta >0$ and maximum clique size $\omega$. Then \[ a(G) \geq \frac{6n}{2Δ+ ω+2}. \] This bound is sharp for cliques. 2. Let $G=(V,E)$ be a triangle-free graph and let $d(v)$ denote the degree of $v\in V$. Then \[ a(G) \geq \sum_{v \in V} \min\left(1, \frac{3}{d(v)+2} \right). \] As a corollary we have that a triangle-free graph $G$ of order $n$, with $m$ edges and average degree $d\ge 2$ satisfies \[ a(G) \geq \frac{3n}{d+2}. \] This improves the lower bound $n-\frac{m}{4}$ of Alon-Mubayi-Thomas for graphs of average degree greater than $4$. Furthermore it improves the lower bound $\frac{20n-5m-5}{19}$ of Shi-Xu for (connected) graphs of average degree at least $\frac{9}{2}$.