Groupe d’études et de recherche en analyse des décisions

# On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set

## Odile Marcotte, Alain Hertz et David Schindl

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 $n - \left \lceil 2 \sqrt{n-1} \right \rceil$. In the special case where n is of the form a2+1 for some even integer $a \geq 4$, f-t is at most $n - \left \lceil 2 \sqrt{n-1} \right \rceil - 1$. We also prove that these bounds are tight. In addition, letting $\alpha$ denote the stability number of G, we show that $\alpha - t$ is at most $n + 1 - \left \lceil 2 \sqrt{2n}\right \rceil$; this bound is also tight.

, 17 pages