A Caro-Wei bound for induced linear forests in graphs

Abstract

A well-known result due to Caro (1979) and Wei (1981) states that every graph $G$ has an independent set of size at least ${\sum }_{v\in V(G)}\frac{1}{d(v)+1}$, where $d(v)$ denotes the degree of vertex $v$. Alon, Kahn, and Seymour (1987) showed the following generalization: For every $k\ge 0$, every graph $G$ has a $k$-degenerate induced subgraph with at least ${\sum }_{v\in V(G)}\min \{1,\frac{k+1}{d(v)+1}\}$ vertices. In particular, for $k=1$, every graph $G$ with no isolated vertices has an induced forest with at least ${\sum }_{v\in V(G)}\frac{2}{d(v)+1}$ vertices. Akbari, Amanihamedani, Mousavi, Nikpey, and Sheybani (2019) conjectured that, if $G$ has minimum degree at least $2$, then one can even find an induced linear forest of that order in $G$, that is, a forest where each component is a path. In this paper, we prove this conjecture and show a number of related results. In particular, if there is no restriction on the minimum degree of $G$, we show that there are infinitely many ``best possible'' functions $f$ such that ${\sum }_{v\in V(G)}f(d(v))$ is a lower bound on the maximum order of a linear forest in $G$, and we give a full characterization of all such functions $f$.

v2: Revised following the referees' comments