摘要 Abstract
我们证明了对于每个完全图 \( K_t \),所有不含同构于 \( K_t \) 的子划分诱导子图的图 \( G \),都存在一个大小至少为 \( |G| / {\rm polylog}|G| \) 的稳定集。这接近最佳结果,因为当 \( t \geq 7 \) 时,不是所有的此类图 \( G \) 都具有线性大小的稳定集,即使 \( G \) 是无三角形的。
We prove that for every complete graph $K_t$, all graphs $G$ with no induced subgraph isomorphic to a subdivision of $K_t$ have a stable subset of size at least $|G|/{\rm polylog}|G|$. This is close to best possible, because for $t\ge 7$, not all such graphs $G$ have a stable set of linear size, even if $G$ is triangle-free.