Large induced forests in sparse graphs
Noga Alon, Dhruv Mubayi, Robin B. Thomas · Journal of Graph Theory · 2001
Abstract For a graph G , let a ( G ) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K 4 , then a ( G ) ≥ n − e/4 − 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a ( G ) ≥ α( G ) + ( n − α( G ))/(Δ − 1) 2 . Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001