论文标题
无钻石图中的强集团
Strong cliques in diamond-free graphs
论文作者
论文摘要
图中的强大集团是一个与所有包含最大最大稳定集相交的集团。强大的集团在完美图的研究中起着重要作用。从结构和算法的角度来看，我们研究了无钻石图的强大集团。我们表明，当限于无钻石图的类别时，以下五个NP或Co-NP硬化问题仍然很棘手：给定的集团是否强？该图有一个强大的集团吗？每个顶点都包含在一个强大的集团中吗？鉴于将顶点设置为集团的划分，分区中的每个集团是否强？可以将顶点集分为强大的集团吗？从积极的一面来看，我们表明，在无钻石图的类别中，可以在线性时间内解决以下两个问题的问题：每个最大集团是否强？每个边缘都包含在一个强大的集团中吗？这些结果源自无钻石图的表征，其中每个最大集团都很强，这也意味着改进了此类图的Erdős-Hajnal特性。
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems remain intractable when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following two problems whose computational complexity is open in general can be solved in linear time in the class of diamond-free graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
