{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T21:05:20Z","timestamp":1775163920039,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T00:00:00Z","timestamp":1709856000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T00:00:00Z","timestamp":1709856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X013642\/1"],"award-info":[{"award-number":["EP\/X013642\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-22-1-0234"],"award-info":[{"award-number":["FA9550-22-1-0234"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["DMS-2154169"],"award-info":[{"award-number":["DMS-2154169"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Gy\u00e1rf\u00e1s\u2013Sumner conjecture says that for every tree <jats:italic>T<\/jats:italic> and every integer <jats:inline-formula><jats:alternatives><jats:tex-math>$$t\\ge 1$$<\/jats:tex-math><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>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, if <jats:italic>G<\/jats:italic> is a graph with no clique of size <jats:italic>t<\/jats:italic> and with sufficiently large chromatic number, then <jats:italic>G<\/jats:italic> contains an induced subgraph isomorphic to <jats:italic>T<\/jats:italic>. This remains open, but we prove that under the same hypotheses, <jats:italic>G<\/jats:italic> contains a subgraph <jats:italic>H<\/jats:italic> isomorphic to <jats:italic>T<\/jats:italic> that is \u201cpath-induced\u201d; that is, for some distinguished vertex\u00a0<jats:italic>r<\/jats:italic>, every path of <jats:italic>H<\/jats:italic> with one end <jats:italic>r<\/jats:italic> is an induced path of <jats:italic>G<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00373-024-02754-z","type":"journal-article","created":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T10:01:42Z","timestamp":1709892102000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Note on the Gy\u00e1rf\u00e1s\u2013Sumner Conjecture"],"prefix":"10.1007","volume":"40","author":[{"given":"Tung","family":"Nguyen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4489-5988","authenticated-orcid":false,"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":[[2024,3,8]]},"reference":[{"key":"2754_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/jgt.22450","volume":"92","author":"M Chudnovsky","year":"2019","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","journal-title":"J. Graph Theory"},{"key":"2754_CR2","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering-numbers. In: Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. II, pp. 801\u2013816. Colloq. Math. Soc. Janos Bolyai, vol. 10. North-Holland, Amsterdam (1975)"},{"key":"2754_CR3","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Proceedings of the International Conference on Combinatorial Analysis and its Applications, (Pokrzywna, 1985), Zastos. Mat., vol. 19, pp. 413\u2013441 (1987)","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"2754_CR4","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A., Szemer\u00e9di, E., Tuza, Zs.: Induced subtrees in graphs of large chromatic number. Discrete Math. 30, 235\u2013344 (1980)","DOI":"10.1016\/0012-365X(80)90230-7"},{"key":"2754_CR5","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":"2754_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0012-365X(95)00187-2","volume":"150","author":"HA Kierstead","year":"1996","unstructured":"Kierstead, H.A., R\u00f6dl, V.: Applications of hypergraph coloring to coloring graphs not inducing certain trees. Discrete Math. 150, 187\u2013193 (1996)","journal-title":"Discrete Math."},{"key":"2754_CR7","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. Discrete Math. 17, 571\u2013581 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"2754_CR8","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":"2754_CR9","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). arXiv:1812.07500","journal-title":"J. Graph Theory"},{"key":"2754_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.103024","volume":"84","author":"A Scott","year":"2020","unstructured":"Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. XIII. New brooms. Eur. J. Combin. 84, 103024 (2020). arXiv:1807.03768","journal-title":"Eur. J. Combin."},{"key":"2754_CR11","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1002\/jgt.22880","volume":"102","author":"A Scott","year":"2023","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). arXiv:2104.07927","journal-title":"J. Graph Theory"},{"key":"2754_CR12","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/jgt.22862","volume":"101","author":"A Scott","year":"2022","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds on chromatic number. III. Excluding a double star. J. Graph Theory 101, 323\u2013340 (2022). arXiv:2108.07066","journal-title":"J. Graph Theory"},{"key":"2754_CR13","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/s00493-023-00015-w","volume":"43","author":"A Scott","year":"2023","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path. Combinatorica 43, 845\u2013852 (2023). arXiv:2110.00278","journal-title":"Combinatorica"},{"key":"2754_CR14","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. Wiley, New York (1981)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02754-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02754-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02754-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T18:03:36Z","timestamp":1714241016000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02754-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,8]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["2754"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02754-z","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,8]]},"assertion":[{"value":"6 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 March 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"33"}}