Graphs Without Large Apples and the Maximum Weight Independent Set Problem
Graphs Without Large Apples and the Maximum Weight Independent Set Problem
复制标题
没有大苹果的图和最大权独立集问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Christopher Purcell
中科院分区：
文献类型：
--
作者：
V. Lozin;Martin Milanič;Christopher Purcell
≥是从长度为k的无弦圈Ck中添加一个在圈上恰好有一个邻居的顶点而得到的图。无苹果图类是无爪图和弦图的共同推广，这两类图具有许多吸引人的性质，包括最大权独立集问题的多项式时间可解性。最近，Brandstädt等人。证明了这一性质推广到了无苹果图类。在本文中，我们研究了这类称为无大苹果图的进一步推广：它们是(AK，AK+1，.。当k=5时，最大权独立集问题的复杂性也是未知的。通过研究没有大苹果的图的结构，我们发现了这类图无爪的一个充分条件。我们证明了有界度和无顶点少项且树宽足够大的图满足这一条件。这意味着对于那些没有大苹果的图的最大权独立集问题是一个有效的解决方案，这些图要么具有有界顶点度，要么排除固定的顶点图作为次要图。
An appleAk is the graph obtained from a chordless cycle Ck of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. The class of apple-free graphs is a common generalization of claw-free graphs and chordal graphs, two classes enjoying many attractive properties, including polynomial-time solvability of the maximum weight independent set problem. Recently, Brandstädt et al. showed that this property extends to the class of apple-free graphs. In the present paper, we study further generalization of this class called graphs without large apples: these are (Ak, Ak+1, . . .)-free graphs for values of k strictly greater than 4. The complexity of the maximum weight independent set problem is unknown even for k = 5. By exploring the structure of graphs without large apples, we discover a sufficient condition for claw-freeness of such graphs. We show that the condition is satisfied by bounded-degree and apex-minor-free graphs of sufficiently large tree-width. This implies an efficient solution to the maximum weight independent set problem for those graphs without large apples, which either have bounded vertex degree or exclude a fixed apex graph as a minor.