{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T08:31:18Z","timestamp":1780043478728,"version":"3.53.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T00:00:00Z","timestamp":1695600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T00:00:00Z","timestamp":1695600000000},"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":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove that, for every graph <jats:italic>F<\/jats:italic> with at least one edge, there is a constant <jats:inline-formula><jats:alternatives><jats:tex-math>$$c_F$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mi>F<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that there are graphs of arbitrarily large chromatic number and the same clique number as <jats:italic>F<\/jats:italic> in which every <jats:italic>F<\/jats:italic>-free induced subgraph has chromatic number at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$c_F$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mi>F<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This generalises recent theorems of Bria\u0144ski, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every <jats:inline-formula><jats:alternatives><jats:tex-math>$$r\\geqslant 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>\u2a7e<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the class of <jats:inline-formula><jats:alternatives><jats:tex-math>$$K_r$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mi>r<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth.<\/jats:p>","DOI":"10.1007\/s00493-023-00061-4","type":"journal-article","created":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T10:01:46Z","timestamp":1695636106000},"page":"37-62","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Induced Subgraphs of Induced Subgraphs of Large Chromatic Number"],"prefix":"10.1007","volume":"44","author":[{"given":"Ant\u00f3nio","family":"Gir\u00e3o","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Freddie","family":"Illingworth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emil","family":"Powierski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Savery","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Youri","family":"Tamitegama","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jane","family":"Tan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,9,25]]},"reference":[{"issue":"2","key":"61_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s004930100016","volume":"21","author":"N Alon","year":"2001","unstructured":"Alon, N., Pach, J., Solymosi, J.: Ramsey-type theorems with forbidden subgraphs. Combinatorica 21(2), 155\u2013170 (2001)","journal-title":"Combinatorica"},{"issue":"3","key":"61_CR2","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1112\/plms\/83.3.532","volume":"83","author":"RC Baker","year":"2001","unstructured":"Baker, R.C., Harman, G., Pintz, J.: The difference between consecutive primes, II. Proc. Lond. Math. Soc. 83(3), 532\u2013562 (2001)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1","key":"61_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2012.08.003","volume":"103","author":"E Berger","year":"2013","unstructured":"Berger, E., Choromanski, K., Chudnovsky, M., Fox, J., Loebl, M., Scott, A., Seymour, P., Thomass\u00e9, S.: Tournaments and colouring. J. Comb. Theory Ser. B 103(1), 1\u201320 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"61_CR4","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02566968","volume":"37","author":"RC Bose","year":"1962","unstructured":"Bose, R.C., Chowla, S.: Theorems in the additive theory of numbers. Commentarii Mathematici Helvetici 37, 141\u2013147 (1962)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"61_CR5","doi-asserted-by":"crossref","unstructured":"Bria\u0144ski, M., Davies, J., Walczak, B.: Separating polynomial $$\\chi $$-boundedness from $$\\chi $$-boundedness. arXiv:2201.08814v1 preprint (2022)","DOI":"10.1007\/s00493-023-00054-3"},{"key":"61_CR6","doi-asserted-by":"crossref","unstructured":"Bria\u0144ski, M., Davies, J., Walczak, B.: Separating polynomial $$\\chi $$-boundedness from $$\\chi $$-boundedness. Combinatorica, to appear (2023)","DOI":"10.1007\/s00493-023-00054-3"},{"key":"61_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.jctb.2022.09.001","volume":"158","author":"A Carbonero","year":"2023","unstructured":"Carbonero, A., Hompe, P., Moore, B., Spirkl, S.: A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number. J. Comb. Theory Ser. B 158, 63\u201369 (2023)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"61_CR8","doi-asserted-by":"crossref","first-page":"352","DOI":"10.2307\/2307489","volume":"61","author":"B Descartes","year":"1954","unstructured":"Descartes, B.: $$k$$-chromatic graphs without triangles. Am. Math. Monthly 61(5), 352\u2013353 (1954)","journal-title":"Am. Math. Monthly"},{"issue":"1","key":"61_CR9","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(1), 161\u2013166 (1950)","journal-title":"Ann. Math."},{"key":"61_CR10","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. Can. J. Math. 11, 34\u201338 (1959)","journal-title":"Can. J. Math."},{"key":"61_CR11","unstructured":"Esperet, L.: Graph colorings, flows and perfect matchings. Habilitation thesis, Universit\u00e9 Grenoble Alpes (2017)"},{"issue":"1","key":"61_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/0118004","volume":"18","author":"J Folkman","year":"1970","unstructured":"Folkman, J.: Graphs with monochromatic complete subgraphs in every edge coloring. SIAM J. Appl. Math. 18(1), 19\u201324 (1970)","journal-title":"SIAM J. Appl. Math."},{"key":"61_CR13","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering-numbers. In: Infinite and Finite Sets (Colloquium, Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), vol. II, Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 10, pp. 801\u2013816. North-Holland, Amsterdam (1975)"},{"key":"61_CR14","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. In: Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastosowania Matematyki, vol. 19, pp. 413\u2013441 (1987)","DOI":"10.4064\/am-19-3-4-413-441"},{"issue":"1","key":"61_CR15","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1090\/S0002-9947-1988-0936824-0","volume":"307","author":"A Hajnal","year":"1988","unstructured":"Hajnal, A., Komj\u00e1th, P.: Embedding graphs into colored graphs. Trans. Am. Math. Soc. 307(1), 395\u2013409 (1988)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"61_CR16","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/S0895480194264769","volume":"10","author":"HA Kierstead","year":"1997","unstructured":"Kierstead, H.A.: Classes of graphs that are not vertex Ramsey. SIAM J. Discret. Math. 10(3), 373\u2013380 (1997)","journal-title":"SIAM J. Discret. Math."},{"key":"61_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(92)90600-K","volume":"101","author":"HA Kierstead","year":"1992","unstructured":"Kierstead, H.A., Trotter, W.T.: Colorful induced subgraphs. Discret. Math. 101, 165\u2013169 (1992)","journal-title":"Discret. Math."},{"issue":"4","key":"61_CR18","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/BF01271268","volume":"16","author":"HA Kierstead","year":"1996","unstructured":"Kierstead, H.A., Zhu, Y.: Classes of graphs that exclude a tree and a clique and are not vertex Ramsey. Combinatorica 16(4), 493\u2013504 (1996)","journal-title":"Combinatorica"},{"issue":"1","key":"61_CR19","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01788077","volume":"2","author":"P Komj\u00e1th","year":"1986","unstructured":"Komj\u00e1th, P., R\u00f6dl, V.: Coloring of universal graphs. Graphs Comb. 2(1), 55\u201360 (1986)","journal-title":"Graphs Comb."},{"issue":"1\u20132","key":"61_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF01872104","volume":"61","author":"P Komj\u00e1th","year":"1993","unstructured":"Komj\u00e1th, P., Shelah, S.: A consistent edge partition theorem for infinite graphs. Acta Mathematica Hungarica 61(1\u20132), 115\u2013120 (1993)","journal-title":"Acta Mathematica Hungarica"},{"key":"61_CR21","unstructured":"Ne\u0161et\u0159il, J.: Teorie graf\u016f. Praha: St\u00e1tn\u00ed Nakladatelstv\u00ed Technick\u00e9 Literatury, 1st edn. (1979)"},{"key":"61_CR22","unstructured":"Ne\u0161et\u0159il, J.: Ramsey theory. In: Handbook of Combinatorics, vol. 2, pp. 1331\u20131403. MIT Press, Cambridge (1996)"},{"key":"61_CR23","unstructured":"Ne\u0161et\u0159il, J.: Personal communication (2023)"},{"issue":"1","key":"61_CR24","first-page":"85","volume":"17","author":"J Ne\u0161et\u0159il","year":"1976","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: Partitions of vertices. Commentationes Mathematicae Universitatis Carolinae 17(1), 85\u201395 (1976)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"issue":"3","key":"61_CR25","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0095-8956(76)90015-0","volume":"20","author":"J Ne\u0161et\u0159il","year":"1976","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: The Ramsey property for graphs with forbidden complete subgraphs. J. Comb. Theory Ser. B 20(3), 243\u2013249 (1976)","journal-title":"J. Comb. Theory Ser. B"},{"key":"61_CR26","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0095-8956(79)90084-4","volume":"27","author":"J Ne\u0161et\u0159il","year":"1979","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: A short proof of the existence of highly chromatic hypergraphs without short cycles. J. Comb. Theory Ser. B 27, 225\u2013227 (1979)","journal-title":"J. Comb. Theory Ser. B"},{"key":"61_CR27","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1090\/S0002-9939-1977-0469806-4","volume":"64","author":"V R\u00f6dl","year":"1977","unstructured":"R\u00f6dl, V.: On the chromatic number of subgraphs of a given graph. Proc. Am. Math. Soc. 64, 370\u2013371 (1977)","journal-title":"Proc. Am. Math. Soc."},{"issue":"4","key":"61_CR28","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/BF01192529","volume":"15","author":"V R\u00f6dl","year":"1995","unstructured":"R\u00f6dl, V., Sauer, N., Zhu, X.: Ramsey families which exclude a graph. Combinatorica 15(4), 589\u2013596 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"61_CR29","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1137\/0402035","volume":"2","author":"V R\u00f6dl","year":"1989","unstructured":"R\u00f6dl, V., Winkler, P.: A Ramsey-type theorem for orderings of a graph. SIAM J. Discret. Math. 2(3), 402\u2013406 (1989)","journal-title":"SIAM J. Discret. Math."},{"issue":"5","key":"61_CR30","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.4153\/CJM-1992-064-7","volume":"44","author":"V R\u00f6dl","year":"1992","unstructured":"R\u00f6dl, V., Sauer, N.: The Ramsey property for families of graphs which exclude a given graph. Can. J. Math. 44(5), 1050\u20131060 (1992)","journal-title":"Can. J. Math."},{"issue":"3","key":"61_CR31","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1090\/S0002-9947-1995-1262340-9","volume":"374","author":"N Sauer","year":"1995","unstructured":"Sauer, N.: On the Ramsey property of families of graphs. Trans. Am. Math. Soc. 374(3), 785\u2013833 (1995)","journal-title":"Trans. Am. Math. Soc."},{"key":"61_CR32","unstructured":"Sauer, N.W., Zhu, X.: Graphs which do not embed a given graph and the Ramsey property. In: Sets, Graphs and Numbers (Budapest. 1991), Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 60, pp. 631\u2013636. North-Holland, Amsterdam (1992)"},{"key":"61_CR33","doi-asserted-by":"crossref","unstructured":"Scott, A.: Graphs of large chromatic number. In: Proceedings of the ICM, to appear (2022)","DOI":"10.4171\/icm2022\/149"},{"key":"61_CR34","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.jctb.2015.10.002","volume":"121","author":"A Scott","year":"2016","unstructured":"Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. I. Odd holes. J. Comb. Theory Ser. B 121, 68\u201384 (2016)","journal-title":"J. Comb. Theory Ser. B"},{"key":"61_CR35","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/j.jctb.2020.01.004","volume":"145","author":"A Scott","year":"2020","unstructured":"Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. VI. Banana trees. J. Comb. Theory Ser. B 145, 487\u2013510 (2020)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"61_CR36","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(3), 473\u2013504 (2020)","journal-title":"J. Graph Theory"},{"key":"61_CR37","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/BF01455900","volume":"106","author":"S Sidon","year":"1932","unstructured":"Sidon, S.: Ein Satz \u00fcber trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen. Math. Ann. 106, 536\u2013539 (1932)","journal-title":"Math. Ann."},{"key":"61_CR38","unstructured":"Sumner, D.P.: Subtrees of a graph and the chromatic number. In: The Theory and Applications of Graphs (Kalamazoo, Michigan, 1980), pp. 557\u2013576. Wiley, New York (1981)"},{"key":"61_CR39","doi-asserted-by":"publisher","first-page":"199","DOI":"10.4064\/aa-27-1-199-245","volume":"27","author":"E Szemer\u00e9di","year":"1975","unstructured":"Szemer\u00e9di, E.: On sets of integers containing no $$k$$ elements in arithmetic progression. Acta Arith. 27, 199\u2013245 (1975)","journal-title":"Acta Arith."},{"key":"61_CR40","first-page":"212","volume":"15","author":"BL van der Waerden","year":"1927","unstructured":"van der Waerden, B.L.: Beweis einer Baudetschen Vermutung. Nieuw Archief voor Wiskunde 15, 212\u2013216 (1927)","journal-title":"Nieuw Archief voor Wiskunde"},{"key":"61_CR41","unstructured":"Zykov, A.: On some properties of linear complexes (in Russian). Matematicheski\u01d0 Sbornik 24, 163\u2013188 (1949). For an English translation see Am. Math. Soc. Transl. 79 (1952)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00061-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00061-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00061-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T22:03:06Z","timestamp":1708552986000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00061-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,25]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["61"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00061-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,25]]},"assertion":[{"value":"18 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}