Subgraph Transversal of Graphs

Given graphs F and G, denote by ({tau_F}(G)) the cardinality of a smallest subset (T {subseteq}V(G)) that meets every maximal F-free subgraph of G. Erdös, Gallai and Tuza [9] considered the question of bounding (tau_{overline{K_2}}(G)) by a constant fraction of |G|. In this paper, we will give a complete answer to the following question: for which F, is τ _F (G) bounded by a constant fraction of |G|?In addition, for those graphs F for which ({tau_F}(G)) is not bounded by any fraction of |G|, we prove that (tau_F(G)le|G|-frac{1}{2}sqrt{|G|}+frac{1}{2}), provided F is not K _k or (overline{K_k}).