Subdivisions and near-linear stable sets

2024/09/14 by Tung Nguyen, Nguyen, Tung, Alex Scott +3
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Combinatorics (math.CO) #FOS: Mathematics #Fuzzy Systems and Optimization #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2409.09400

openalex publication_date 2024/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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≥ 7, not all such graphs G have a stable set of linear size, even if G is triangle-free.

Related

• Trees and near-linear stable sets
• Induced subgraph density. III. Cycles and subdivisions
• The stable set polytope of (P₆,triangle)-free graphs and new facet-inducing graphs
• Pure pairs. II. Excluding all subdivisions of a graph
• Packing subdivisions into regular graphs