Let $G$ be a graph and $a(G)$, LIF$(G)$ denote the maximum orders of an induced forest and an induced linear forest of $G$, respectively. It is well-known that if $G$ is an $r$-regular graph of order $n$, then $a(G) \geq \frac{ 2}{ r+1}n$. In this paper, we generalize this result by showing that LIF$(G) \geq \frac{ 2}{ r+1}n$. It was proved that for every graph $G$, $a(G) \geq \sum_{ i=1}^{ n}\frac{ 2}{ d_i+1}$, where $d_1, \ldots, d_n$ is the degree sequence of $G$. Here, we conjecture that for every graph $G$ with $\delta(G) \geq 2$, LIF$(G) \geq \sum_{ i=1}^{ n}\frac{ 2}{ d_i+1}$.
Categories: math.CO