{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:24:18Z","timestamp":1757615058036,"version":"3.44.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T00:00:00Z","timestamp":1751587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T00:00:00Z","timestamp":1751587200000},"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,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We prove that for every complete graph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$K_t$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mi>t<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, all graphs <jats:italic>G<\/jats:italic> with no induced subgraph isomorphic to a subdivision of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$K_t$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mi>t<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> have a stable subset of size at least <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$|G|\/\\operatorname {polylog}|G|$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mo>polylog<\/mml:mo>\n                    <mml:mo>|<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>|<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. This is close to best possible, because for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$t\\ge 7$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>t<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>7<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, not all such graphs <jats:italic>G<\/jats:italic> have a stable set of linear size, even if <jats:italic>G<\/jats:italic> is triangle-free.<\/jats:p>","DOI":"10.1007\/s00493-025-00154-2","type":"journal-article","created":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T06:01:44Z","timestamp":1751608904000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Subdivisions and near-linear stable sets"],"prefix":"10.1007","volume":"45","author":[{"given":"Tung","family":"Nguyen","sequence":"first","affiliation":[]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Seymour","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,4]]},"reference":[{"key":"154_CR1","first-page":"16","volume":"5","author":"R Bourneuf","year":"2024","unstructured":"Bourneuf, R., Buci\u0107, M., Cook, L., Davies, J.: On polynomial degree-boundedness. Adv Combin. 5, 16 (2024)","journal-title":"Adv Combin."},{"key":"154_CR2","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Esperet, L., Li, Z., Ossona de Mendez, P.: Restricted frame graphs and a conjecture of Scott\u201d, Electronic J. Combinatorics 23 (2016), Preprint at arXiv:1406.0338","DOI":"10.37236\/4424"},{"key":"154_CR3","doi-asserted-by":"publisher","unstructured":"Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Pure pairs. I. Trees and linear anticomplete pairs. Adv. Math. 375, 107396 (2020). https:\/\/doi.org\/10.1016\/j.aim.2020.107396. arXiv:1809.00919","DOI":"10.1016\/j.aim.2020.107396"},{"key":"154_CR4","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00493-020-4024-1","volume":"41","author":"M Chudnovsky","year":"2021","unstructured":"Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Pure pairs. II. Excluding all subdivisions of a graph. Combinatorica 41, 279\u2013405 (2021). arXiv:1804.01060","journal-title":"Combinatorica"},{"key":"154_CR5","doi-asserted-by":"crossref","unstructured":"Du, X, Rose, M: A survey of degree-boundedness, Europ J Combin (2024), p. 104092, Preprint at arXiv:2403.05737","DOI":"10.1016\/j.ejc.2024.104092"},{"key":"154_CR6","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":"154_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1017\/S0963548313000412","volume":"23","author":"J Fox","year":"2014","unstructured":"Fox, J., Pach, J.: Applications of a new separator theorem for string graphs. Comb. Probab. Comput. 23, 66\u201374 (2014)","journal-title":"Comb. Probab. Comput."},{"key":"154_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103811","volume":"119","author":"J Fox","year":"2024","unstructured":"Fox, J., Pach, J., Suk, A.: Quasiplanar graphs, string graphs, and the Erd\u0151s-Gallai problem. European J. Comb. 119, 103811 (2024)","journal-title":"European J. Comb."},{"key":"154_CR9","unstructured":"Gir\u00e3o, A., Hunter, Z.: Induced subdivisions in $$K_{s,s}$$-free graphs with polynomial average degree, Preprint at arXiv:2310.18452"},{"key":"154_CR10","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering-numbers, Coll. Math. Soc. J\u00e1nos Bolyai, in infinite and finite sets, North Holland\/American Elsevier, New York (1975)"},{"key":"154_CR11","doi-asserted-by":"crossref","unstructured":"Hunter, Z., Milojevi\u0107, A., Sudakov, B., Tomon, I.: \u201cK\u0151v\u00e1ri-S\u00f3s-Tur\u00e1n theorem for hereditary families\u201d, (2024), J. Combinatorial Theory Ser. B 172 (2025), 168\u2013197, Preprint at arxiv:2401.10853","DOI":"10.1016\/j.jctb.2024.12.009"},{"key":"154_CR12","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":"154_CR13","doi-asserted-by":"crossref","unstructured":"Korhonen, T., Lokshtanov, D.: \u201cInduced-minor-free graphs: separator theorem, subexponential algorithms, and improved hardness of recognition\u201d, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, (2024) Preprint at arXiv:2308.04795","DOI":"10.1137\/1.9781611977912.188"},{"key":"154_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00493-004-0017-8","volume":"24","author":"D K\u00fchn","year":"2004","unstructured":"K\u00fchn, D., Osthus, D.: Induced subdivisions in $$K_{s, s}$$-free graphs of large average degree. Combinatorica 24, 287\u2013304 (2004)","journal-title":"Combinatorica"},{"key":"154_CR15","unstructured":"Nguyen, T.: Induced subgraph density, Ph.D. Thesis, Princeton University, May 2025, in preparation"},{"key":"154_CR16","doi-asserted-by":"crossref","unstructured":"Nguyen, T., Scott, A., Seymour, P.: \u201cTrees and near-linear stable sets\u201d, manuscript May 2024, Preprint at arXiv:2409.09397","DOI":"10.1007\/s00493-025-00154-2"},{"key":"154_CR17","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.jctb.2013.11.001","volume":"105","author":"A Pawlik","year":"2014","unstructured":"Pawlik, A., Kozik, J., Krawczyk, T., Laso\u0144, M., Micek, P., Trotter, W.T., Walczak, B.: Triangle-free intersection graphs of line segments with large chromatic number,. J. Comb. Theory Ser. B 105, 6\u201310 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"key":"154_CR18","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":"154_CR19","doi-asserted-by":"publisher","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree. J. Graph Theory 102, 458\u2013471 (2023). https:\/\/doi.org\/10.1002\/jgt.22880. arXiv:2104.07927","DOI":"10.1002\/jgt.22880"},{"key":"154_CR20","unstructured":"Sumner, D.P.: Subtrees of a graph and chromatic number, in The theory and applications of graphs, (G. Chartrand, ed.), Wiley, New York, 557\u2013576 (1981)"},{"key":"154_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00454-014-9645-y","volume":"53","author":"B Walczak","year":"2015","unstructured":"Walczak, B.: Triangle-free geometric intersection graphs with no large independent set. Discrete Comb. Geometry 53, 221\u2013225 (2015)","journal-title":"Discrete Comb. Geometry"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00154-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00154-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00154-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T12:38:38Z","timestamp":1757075918000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00154-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,4]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["154"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00154-2","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,7,4]]},"assertion":[{"value":"14 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"39"}}