Some bounds on the size of maximum G-free sets in graphs.

For a given graph H , the independence number α (H) of H is the size of the maximum independent set of V (H). Finding the maximum independent set in a graph is NP-hard. Another version of the independence number is defined as the size of the maximum-induced forest of H , and called the forest number of H , and denoted by f (H). Finding f (H) is also an NP-hard problem. Suppose that H = (V (H) , E (H)) is a graph, and is a family of graphs, a graph H has a -free k -coloring if there exists a decomposition of V (H) into sets V i , i = 1 , 2 , ... , k , so that G ⊈ H [ V i ] for each i , and each G ∈ . S ⊆ V (H) is G -free, if the subgraph of H induced by S is G -free, i.e., it contains no copy of G. Finding a maximum subset S of H , such that H [ S ] is a G -free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also, we give some bounds about the size of the maximum G -free subset of graphs as another purpose of this paper. [ABSTRACT FROM AUTHOR]