We prove that for every complete graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_154_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation>, all graphs G with no induced subgraph isomorphic to a subdivision of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_154_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> have a stable subset of size at least <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_154_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="116" /> </InlineMediaObject> <EquationSource Format="TEX">$|G|/\operatorname {polylog}|G|$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>G</mi> <mo stretchy="false">|</mo> <mo stretchy="false">/</mo> <mo>polylog</mo> <mo stretchy="false">|</mo> <mi>G</mi> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>. This is close to best possible, because for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_154_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$t\ge 7$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation>, not all such graphs G have a stable set of linear size, even if G is triangle-free.

Subdivisions and near-linear stable sets

期刊论文
出版模式：

开放获取
发表日期：

2025年7月4日

查看全文

Tung Nguyen,
Alex Scott,
Paul Seymour

摘要

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