论文标题
独立集（$ p_4+p_4 $，三角形） - 免费图形
Independent sets in ($P_4+P_4$,Triangle)-free graphs
论文作者
论文摘要
最大重量独立设置问题（WIS）是一个众所周知的NP硬性问题。研究WIS的一种流行方法是检测图形类别，可以在多项式时间内解决WIS，特别是参考遗传图类别，即由遗传图属性定义，或者是通过禁止一个或多个引起的子绘图的。给定两个图表$ g $和$ h $，$ g+h $表示$ g $和$ h $的脱节结合。本手稿表明，（i）WIS可以用于（$ p_4+p_4 $，三角形） - 多项式时间中的无图形，其中$ p_4 $是四个顶点的诱导路径，三角形是三个顶点的周期，尤其是（尤其是$ p_4+p _ $ p_ $ g $ g $ g $ g） $ v（g）$诱导（完整）$ g $的$ v（g）$的子集的s} $，其中包含多项式的许多成员，并且可以在多项式时间内计算，以便在$ {\ cal s} $的某些成员中包含$ g $的每个最大独立集。对于某些[$ s_ {i，j，k} $的某些[子类别的子类别，免费图形）与其他多项式结果相对于其他多项式结果而言是和谐的 - 免费图和其他结构结果在不含三角形的图的[子类]上。
The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs $G$ and $H$, $G+H$ denotes the disjoint union of $G$ and $H$. This manuscript shows that (i) WIS can be solved for ($P_4+P_4$, Triangle)-free graphs in polynomial time, where a $P_4$ is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every ($P_4+P_4$, Triangle)-free graph $G$ there is a family ${\cal S}$ of subsets of $V(G)$ inducing (complete) bipartite subgraphs of $G$, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of $G$ is contained in some member of ${\cal S}$. These results seem to be harmonic with respect to other polynomial results for WIS on certain [subclasses of] $S_{i,j,k}$-free graphs and to other structure results on [subclasses of] Triangle-free graphs.
