Let G be a connected graph, n the order of G, and f (resp. t) the maximum order of an induced forest (resp. tree) in G. We show that f-t is at most . In the special case where n is of the form a2+1 for some even integer , f-t is at most . We also prove that these bounds are tight. In addition, letting denote the stability number of G, we show that is at most ; this bound is also tight.
Paru en septembre 2011 , 17 pages