New results on large induced forests in graphs

For a graph $G$ , let $a (G)$ denote the maximum size of a subset of vertices that induces a forest. We prove the following.

Let $G$ be a graph of order $n$ , maximum degree $Δ > 0$ and maximum clique size $ω$ . Then $a (G) \geq \frac{6 n}{2 Δ + ω + 2} .$ This bound is sharp for cliques.
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 (1, \frac{3}{d (v) + 2}) .$ As a corollary we have that a triangle-free graph $G$ of order $n$ , with $m$ edges and average degree $d \geq 2$ satisfies $a (G) \geq \frac{3 n}{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{20 n - 5 m - 5}{19}$ of Shi-Xu for (connected) graphs of average degree at least $\frac{9}{2}$ .

For a graph $G$ , let $a (G)$ denote the maximum size of a subset of vertices that induces a forest. We prove the following.

Let $G$ be a graph of order $n$ , maximum degree $Δ > 0$ and maximum clique size $ω$ . Then $a (G) \geq \frac{6 n}{2 Δ + ω + 2} .$ This bound is sharp for cliques.
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 (1, \frac{3}{d (v) + 2}) .$ As a corollary we have that a triangle-free graph $G$ of order $n$ , with $m$ edges and average degree $d \geq 2$ satisfies $a (G) \geq \frac{3 n}{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{20 n - 5 m - 5}{19}$ of Shi-Xu for (connected) graphs of average degree at least $\frac{9}{2}$ .

文献摘要