论文标题

图中最大$ g $ free集的大小的一些界限

Some bounds on the size of Maximum $G$-free sets in graph

论文作者

Rowshan, Yaser

论文摘要

对于给定的图形$ 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.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源