{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T04:26:06Z","timestamp":1784694366122,"version":"3.55.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:00:00Z","timestamp":1694736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:00:00Z","timestamp":1694736000000},"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":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph<jats:italic>G<\/jats:italic>is<jats:italic>H<\/jats:italic><jats:italic>-free<\/jats:italic>if it has no induced subgraph isomorphic to<jats:italic>H<\/jats:italic>. We prove that a<jats:inline-formula><jats:alternatives><jats:tex-math>$$P_5$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>P<\/mml:mi><mml:mn>5<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graph with clique number<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega \\ge 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03c9<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>has chromatic number at most<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega ^{\\log _2(\\omega )}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>\u03c9<\/mml:mi><mml:mrow><mml:msub><mml:mo>log<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>\u03c9<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The best previous result was an exponential upper bound<jats:inline-formula><jats:alternatives><jats:tex-math>$$(5\/27)3^{\\omega }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>5<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>27<\/mml:mn><mml:mo>)<\/mml:mo><\/mml:mrow><mml:msup><mml:mn>3<\/mml:mn><mml:mi>\u03c9<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erd\u0151s-Hajnal conjecture holds for<jats:inline-formula><jats:alternatives><jats:tex-math>$$P_5$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>P<\/mml:mi><mml:mn>5<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for<jats:inline-formula><jats:alternatives><jats:tex-math>$$P_5$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>P<\/mml:mi><mml:mn>5<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs, and our result is an attempt to approach that.<\/jats:p>","DOI":"10.1007\/s00493-023-00015-w","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T09:06:00Z","timestamp":1694768760000},"page":"845-852","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path"],"prefix":"10.1007","volume":"43","author":[{"given":"Alex","family":"Scott","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Seymour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,9,15]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Blanco, P., Buci\u0107, M.: \u201cTowards the Erd\u0151s\u2013Hajnal conjecture for $$P_5$$-free graphs\u201d, manuscript, September (2022)","DOI":"10.1007\/s40687-023-00413-y"},{"key":"15_CR2","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2201.08814","author":"M Bria\u0144ski","year":"2022","unstructured":"Bria\u0144ski, M., Davies, J., Walczak, B.: Separating polynomial $$\\chi $$-boundedness from $$\\chi $$-boundedness. arXiv:2201.08814 (2022). https:\/\/doi.org\/10.48550\/arXiv.2201.08814","journal-title":"arXiv:2201.08814"},{"key":"15_CR3","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)","journal-title":"J. Graph Theory"},{"key":"15_CR4","doi-asserted-by":"publisher","unstructured":"Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Erd\u0151s-Hajnal for graphs with no 5-hole. Proceedings of the London Math. Soc. 126, 997\u20131014, arXiv:2102.04994 (2023). https:\/\/doi.org\/10.1112\/plms.12504","DOI":"10.1112\/plms.12504"},{"key":"15_CR5","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2202.10412","author":"M Chudnovsky","year":"2022","unstructured":"Chudnovsky, M., Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds for chromatic number VI Adding a four-vertex path. Eur. J. Combinatorics (2022). https:\/\/doi.org\/10.48550\/arXiv.2202.10412","journal-title":"Eur. J. Combinatorics"},{"key":"15_CR6","unstructured":"Erd\u0151s, P., Hajnal, A.: \u201cOn spanned subgraphs of graphs\u201d, Graphentheorie und Ihre Anwendungen (Oberhof, 1977)"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(89)90045-0","volume":"25","author":"P Erd\u0151s","year":"1989","unstructured":"Erd\u0151s, P., Hajnal, A.: Ramsey-type theorems. Discrete Appl. Math. 25, 37\u201352 (1989)","journal-title":"Discrete Appl. Math."},{"key":"15_CR8","unstructured":"Esperet, L.: Graph Colorings, Flows and Perfect Matchings, Habilitation thesis, Universit\u00e9 Grenoble Alpes (2017), 24, https:\/\/tel.archives-ouvertes.fr\/tel-01850463\/document"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1016\/j.disc.2012.12.019","volume":"313","author":"L Esperet","year":"2013","unstructured":"Esperet, L., Lemoine, L., Maffray, F., Morel, G.: The chromatic number of $$\\{P_5, K_4\\}$$-free graphs. Discrete Math. 313, 743\u2013754 (2013)","journal-title":"Discrete Math."},{"key":"15_CR10","first-page":"801","volume":"2","author":"A Gy\u00e1rf\u00e1s","year":"1975","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering-numbers. Infinite Finite Sets 2, 801\u2013816 (1975)","journal-title":"Infinite Finite Sets"},{"key":"15_CR11","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","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), Pokrzywna Zastos. Mat. 19, 413\u2013441 (1987)","journal-title":"Proceedings of the International Conference on Combinatorial Analysis and its Applications, (Pokrzywna, 1985), Pokrzywna Zastos. Mat."},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0012-365X(80)90230-7","volume":"30","author":"A Gy\u00e1rf\u00e1s","year":"1980","unstructured":"Gy\u00e1rf\u00e1s, A., Szemer\u00e9di, E., Tuza, Zs.: Induced subtrees in graphs of large chromatic number. Discrete Math 30, 235\u2013344 (1980)","journal-title":"Discrete Math"},{"key":"15_CR13","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":"15_CR14","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":"15_CR15","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2106.08871","author":"X Liu","year":"2021","unstructured":"Liu, X., Schroeder, J., Wang, Z., Yu, X.: Polynomial $$\\chi $$-binding functions for $$t$$-broom-free graphs. arXiv:2106.08871 (2021). https:\/\/doi.org\/10.48550\/arXiv.2106.08871","journal-title":"arXiv:2106.08871"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-018-1999-0","volume":"35","author":"I Schiermeyer","year":"2019","unstructured":"Schiermeyer, I., Randerath, B.: Polynomial $$\\chi $$-binding functions and forbidden induced subgraphs: a survey. Graphs Combinatorics 35, 1\u201331 (2019)","journal-title":"Graphs Combinatorics"},{"key":"15_CR17","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":"15_CR18","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 (2020a)","journal-title":"J. Graph Theory"},{"key":"15_CR19","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. Combinatorics 84, 103024 (2020b)","journal-title":"XIII. New brooms. Eur. J. Combinatorics"},{"key":"15_CR20","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2202.05557","author":"A Scott","year":"2022","unstructured":"Scott, A., Seymour, P.: Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph. arXiv:2202.05557 (2022). https:\/\/doi.org\/10.48550\/arXiv.2202.05557","journal-title":"arXiv:2202.05557"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds on chromatic number. II. Excluding a star-forest. J. Graph Theory 101, 318\u2013322 (2022a). arXiv:2107.11780","DOI":"10.1002\/jgt.22829"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds on chromatic number. III. Excluding a double star. J. Graph Theory 101, 323\u2013340 (2022b)","DOI":"10.1002\/jgt.22862"},{"issue":"3","key":"15_CR23","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 on chromatic number I Excluding a biclique and an induced tree. J. Graph Theory 102(3), 458\u2013471 (2023)","journal-title":"J. Graph Theory"},{"key":"15_CR24","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche, D.: On a property of the class of $$n$$-colorable graphs. J. Combin. Theory, Ser. B 16, 191\u2013193 (1974)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"15_CR25","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":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00015-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00015-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00015-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T21:12:02Z","timestamp":1703193122000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00015-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,15]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["15"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00015-w","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,15]]},"assertion":[{"value":"1 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}