{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:06:28Z","timestamp":1761599188148,"version":"build-2065373602"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T00:00:00Z","timestamp":1758758400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T00:00:00Z","timestamp":1758758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    When\n                    <jats:italic>H<\/jats:italic>\n                    is a forest, the Gy\u00e1rf\u00e1s-Sumner conjecture implies that every graph\n                    <jats:italic>G<\/jats:italic>\n                    with no induced subgraph isomorphic to\n                    <jats:italic>H<\/jats:italic>\n                    and with bounded clique number has a stable set of linear size. We cannot prove that, but we prove that every such graph\n                    <jats:italic>G<\/jats:italic>\n                    has a stable set of size\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$|G|^{1-o(1)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mo>|<\/mml:mo>\n                              <mml:mi>G<\/mml:mi>\n                              <mml:mo>|<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>-<\/mml:mo>\n                              <mml:mi>o<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . If\n                    <jats:italic>H<\/jats:italic>\n                    is not a forest, there need not be such a stable set. Second, we prove that when\n                    <jats:italic>H<\/jats:italic>\n                    is a \u201cmultibroom\u201d, there is a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a \u201cfractional colouring\u201d version of the Gy\u00e1rf\u00e1s-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting.\n                  <\/jats:p>","DOI":"10.1007\/s00493-025-00177-9","type":"journal-article","created":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T10:50:02Z","timestamp":1758797402000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Trees and near-linear stable sets"],"prefix":"10.1007","volume":"45","author":[{"given":"Tung","family":"Nguyen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Seymour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,25]]},"reference":[{"key":"177_CR1","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. xii. Distant stars. J. Graph Theory 92, 237\u2013254 (2019). arXiv:1711.08612","DOI":"10.1002\/jgt.22450"},{"key":"177_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.jctb.2013.11.002","volume":"105","author":"M Chudnovsky","year":"2014","unstructured":"Chudnovsky, M., Seymour, P.: Extending the gy\u00e1rf\u00e1s-sumner conjecture. J. Comb. Theory, Ser B 105, 11\u201316 (2014)","journal-title":"J. Comb. Theory, Ser B"},{"key":"177_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.jctb.2014.01.001","volume":"106","author":"M Chudnovsky","year":"2014","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.: Excluding pairs of graphs. J. Comb. Theory, Ser B 106, 15\u201329 (2014)","journal-title":"J. Comb. Theory, Ser B"},{"key":"177_CR4","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability. Canad. J. Math. 11, 34\u201338 (1959)","journal-title":"Canad. J. Math."},{"key":"177_CR5","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering-numbers. Infinite and Finite Sets 2, 801\u2013816 (1975)"},{"key":"177_CR6","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Proc. of the Int. Conf. on Comb. Anal. and its Appl. (Pokrzywna, 1985), Zastos. Mat. 19, 413\u2013441 (1987)","journal-title":"Proc. of the Int. Conf. on Comb. Anal. and its Appl. (Pokrzywna, 1985), Zastos. Mat."},{"key":"177_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1002\/jgt.3190180203","volume":"18","author":"HA Kierstead","year":"1994","unstructured":"Kierstead, H.A., Penrice, S.G.: Radius two trees specify $$\\chi $$-bounded classes. J. Graph Theory 18, 119\u2013129 (1994)","journal-title":"J. Graph Theory"},{"key":"177_CR8","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/S0895480198339869","volume":"17","author":"HA Kierstead","year":"2004","unstructured":"Kierstead, H.A., Zhu, Y.: Radius three trees in graphs with large chromatic number. SIAM J. Disc. Math. 17, 571\u2013581 (2004)","journal-title":"SIAM J. Disc. Math."},{"key":"177_CR9","unstructured":"Nguyen, T., Scott, A., Seymour, P.: Induced subgraph density. V. All paths approach Erd\u0151s-Hajnal. Submitted for publication, arXiv:2307.15032"},{"key":"177_CR10","doi-asserted-by":"crossref","unstructured":"Nguyen, T., Scott, A., Seymour, P.: A note on the Gy\u00e1rf\u00e1s-Sumner conjecture. Graphs and Comb. 40, 33 (2024)","DOI":"10.1007\/s00373-024-02754-z"},{"key":"177_CR11","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1002\/jgt.23129","volume":"107","author":"T Nguyen","year":"2024","unstructured":"Nguyen, T., Scott, A., Seymour, P.: Polynomial bounds for chromatic number. viii. excluding a path and a complete multipartite graph. J. Graph Theory 107, 509\u2013521 (2024). arXiv:2303.11766","journal-title":"J. Graph Theory"},{"key":"177_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.0.CO;2-J","volume":"24","author":"A Scott","year":"1997","unstructured":"Scott, A.: Induced trees in graphs of large chromatic number. J. Graph Theory 24, 297\u2013311 (1997)","journal-title":"J. Graph Theory"},{"key":"177_CR13","doi-asserted-by":"crossref","unstructured":"Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. XIII. New brooms. Eur. J. Comb. 84, 103024 (2020). arXiv:1807.03768","DOI":"10.1016\/j.ejc.2019.103024"},{"key":"177_CR14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/jgt.22601","volume":"95","author":"A Scott","year":"2020","unstructured":"Scott, A., Seymour, P.: A survey of $$\\chi $$-boundedness. J. Graph Theory 95, 473\u2013504 (2020)","journal-title":"J. Graph Theory"},{"key":"177_CR15","doi-asserted-by":"crossref","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds for chromatic number. ii. Excluding a star forest. J. Graph Theory 101, 318\u2013322 (2022). arXiv:2107.11780","DOI":"10.1002\/jgt.22829"},{"key":"177_CR16","doi-asserted-by":"crossref","unstructured":"Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discrete Math. 20, 69\u201376 (1977)","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"177_CR17","unstructured":"Spirkl, S.: Cliques, Stable Sets, and Coloring in Graphs with Forbidden Induced Subgraphs, Ph.D. thesis, Princeton University (2018)"},{"key":"177_CR18","first-page":"557","volume-title":"The Theory and Applications of Graphs","author":"DP Sumner","year":"1981","unstructured":"Sumner, D.P.: Subtrees of a graph and chromatic number. In: Chartrand, G. (ed.) The Theory and Applications of Graphs, pp. 557\u2013576. John Wiley & Sons, New York (1981)"},{"key":"177_CR19","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok (in Hungarian) 48, 436\u2013452 (1941)","journal-title":"Matematikai \u00e9s Fizikai Lapok (in Hungarian)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00177-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00177-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00177-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:02:24Z","timestamp":1761598944000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00177-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,25]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["177"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00177-9","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,9,25]]},"assertion":[{"value":"14 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"49"}}