Subdivisions and near-linear stable sets

Tung Nguyen; Alex Scott; Paul Seymour

doi:10.1007/s00493-025-00154-2

Subdivisions and near-linear stable sets

Tung Nguyen
, Alex Scott
, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that for every complete graph Kt, all graphs G with no induced subgraph isomorphic to a subdivision of Kt have a stable subset of size at least |G|/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.

Original language	English (US)
Article number	39
Journal	Combinatorica
Volume	45
Issue number	4
DOIs	https://doi.org/10.1007/s00493-025-00154-2
State	Published - Aug 2025

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-025-00154-2

Cite this

@article{35c903f00ede47ea8b7f4652833af383,

title = "Subdivisions and near-linear stable sets",

abstract = "We prove that for every complete graph Kt, all graphs G with no induced subgraph isomorphic to a subdivision of Kt have a stable subset of size at least |G|/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.",

author = "Tung Nguyen and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2025.",

year = "2025",

month = aug,

doi = "10.1007/s00493-025-00154-2",

language = "English (US)",

volume = "45",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - Subdivisions and near-linear stable sets

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

N1 - Publisher Copyright: © The Author(s) 2025.

PY - 2025/8

Y1 - 2025/8

N2 - We prove that for every complete graph Kt, all graphs G with no induced subgraph isomorphic to a subdivision of Kt have a stable subset of size at least |G|/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.

AB - We prove that for every complete graph Kt, all graphs G with no induced subgraph isomorphic to a subdivision of Kt have a stable subset of size at least |G|/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.

UR - https://www.scopus.com/pages/publications/105010123561

UR - https://www.scopus.com/pages/publications/105010123561#tab=citedBy

U2 - 10.1007/s00493-025-00154-2

DO - 10.1007/s00493-025-00154-2

M3 - Article

AN - SCOPUS:105010123561

SN - 0209-9683

VL - 45

JO - Combinatorica

JF - Combinatorica

IS - 4

M1 - 39

ER -

Subdivisions and near-linear stable sets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this