Combinatorica Computational Mathematics

Subdivisions and near-linear stable sets

Tung Nguyen, Alex Scott, Paul Seymour
Springer Nature · 2025-07-04 · DOI 10.1007/s00493-025-00154-2

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.

Read at publisher →