Hitting all maximum cliques with a stable set using lopsided independent transversals
Hitting all maximum cliques with a stable set using lopsided independent transversals
复制标题
使用不平衡的独立横截面以稳定的集合击中所有最大派系
DOI：
--
复制
发表时间：
2009
影响因子：
0.9
通讯作者：
Andrew D. King
中科院分区：
文献类型：
--
作者：
Andrew D. King
Rabern 最近证明，任何图 都包含满足所有最大派系的稳定集。我们强化了这个结果，证明对于任何具有 的图都存在这样一个稳定的集合。这是严格的，即声明中的不等式必须是严格的。该证明依赖于在划分为大小不等的顶点集的图中找到独立的横截面。 © 2010 Wiley periodicals, Inc. J 图论 67:300‐305, 2011
Rabern recently proved that any graph with contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with . This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:300‐305, 2011