Trees and near-linear stable sets

Abstract 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)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>G</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> . 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.