Trees and near-linear stable sets

期刊论文
出版模式：

开放获取
发表日期：

2025年9月25日

查看全文

Tung Nguyen,
Alex Scott,
Paul Seymour

摘要

When H is a forest, the Gyárfás-Sumner conjecture implies that every graph G with no induced subgraph isomorphic to H and with bounded clique number has a stable set of linear size. We cannot prove that, but we prove that every such graph G has a stable set of size $|G|^{1-o(1)}$ ${| G |}^{1 - o (1)}$ . If H is not a forest, there need not be such a stable set. Second, we prove that when H is a “multibroom”, there is a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a “fractional colouring” version of the Gyárfás-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting.