We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Some bounds on the size of maximum G-free sets in graphs.
- Authors
Rowshan, Yaser
- Abstract
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.
- Subjects
NP-hard problems; INDEPENDENT sets; RAMSEY numbers
- Publication
Discrete Mathematics, Algorithms & Applications, 2023, Vol 15, Issue 5, p1
- ISSN
1793-8309
- Publication type
Article
- DOI
10.1142/S1793830922501324