Graphs with large minimum degree containing no copy of a clique on $r$ vertices ($K_r$) must contain relatively large independent sets. A classical result of Andrásfai, Erd?s, and Sós implies that $K_r$-free graphs $G$ with degree larger than $((3r-7)/(3r-4))|V(G)|$ must be $(r-1)$-partite. An obvious consequence of this result is that the same degree threshold implies an independent set of order $(1/(r-1))|V(G)|$.?The following paper provides improved bounds on the minimum degree which would imply the same conclusion. This problem was first considered by Brandt, and we provide improvements over these initial results for $r 5$.
展开▼
机译：最小度数较大的图形不包含$ r $顶点（$ K_r $）上的小集团的副本，则必须包含相对较大的独立集。 Andrásfai，Erd？s和Sós的经典结果意味着，度数大于$（（（3r-7）/（3r-4））| V（G）| $的无$ K_r $的图$ G $ $（r-1）$-partite。该结果的明显结果是，相同的度阈值意味着一个独立的阶次$（1 /（r-1））| V（G）| $。？以下论文提供了最小度的改进边界，这意味着同样的结论。布兰特首先考虑了这个问题，并且我们针对$ r> 5 $的这些初始结果进行了改进。
展开▼
