论文标题
图中最大$ g $ free集的大小的一些界限
Some bounds on the size of Maximum $G$-free sets in graph
论文作者
论文摘要
对于给定的图形$ h $，独立数$α（h）$ $ h $，是$ v（h）$的最大独立集的大小。在图中查找最大独立集是NP硬性问题。独立号码的另一个版本定义为$ h $的最大诱发森林的大小，称为$ h $的森林数，并用$ f（h）$表示。查找$ f（h）$也是一个NP硬性问题。假设$ h =（v（h），e（h））$是图形，而$ \ g $是一个图形，图$ h $具有$ \ g $ -free $ k $ -o-coloring如果存在$ v（h）$的分解为$ v（h）$ s sets $ v_i $ v_i $，$ v_i $，$ v_i $，$ i-1,2 $，$ i-1,2，k $ g \ g \ ns ns for nsse， $ i $和$ g \ in \ g $。 $ s \ subseteq v（h）$是$ g $ - free，其中$ s $引起的$ h $的子图是$ g $ -free，即不包含$ g $的副本。找到$ h $的最大子集，因此$ h [s] $ be a $ g $ - free图也是一个非常困难的问题。在本文中，我们研究了图的独立数的广义版。本文的另一个目的也是关于最大$ g $ - 免费子集的最大$ G $ - 免费子集的大小的界限。
For 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 a NP-hard problem. 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 a NP-hard problem. Suppose that $H=(V(H),E(H))$ be a graph, and $\G$ be a family of graphs, a graph $H$ has a $\G$-free $k$-coloring if there exists a decomposition of $V(H)$ into sets $V_i$, $i-1,2,\ldots,k$, so that $G\nsubseteq H[V_i]$ for each $i$, and $G\in\G$. $S\subseteq V(H)$ is $G$-free, where the subgraph of $H$ induced by $S$, be $G$-free, i.e. it contains no copy of $G$. Finding a maximum subset of $H$, so that $H[S]$ be 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 giving some bounds about the size of the maximum $G$-free subset of graphs is another purpose of this article.
