Combinatorica Computational Mathematics
Subdivisions and near-linear stable sets
Abstract
Abstract We prove that for every complete graph $$K_t$$ K t , all graphs G with no induced subgraph isomorphic to a subdivision of $$K_t$$ K t have a stable subset of size at least $$|G|/\operatorname {polylog}|G|$$ | G | / polylog | G | . This is close to best possible, because for $$t\ge 7$$ t ≥ 7 , not all such graphs G have a stable set of linear size, even if G is triangle-free.