{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T12:30:22Z","timestamp":1713184222059},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T00:00:00Z","timestamp":1675209600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T00:00:00Z","timestamp":1683849600000},"content-version":"vor","delay-in-days":100,"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,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given an <jats:inline-formula><jats:alternatives><jats:tex-math>$$(r + 1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-chromatic graph <jats:italic>H<\/jats:italic>, the fundamental edge stability result of Erd\u0151s and Simonovits says that all <jats:italic>n<\/jats:italic>-vertex <jats:italic>H<\/jats:italic>-free graphs have at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1 - 1\/r + o(1)) \\binom{n}{2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:mi>o<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mfenced>\n                      <mml:mfrac>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:mfrac>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges, and any <jats:italic>H<\/jats:italic>-free graph with that many edges can be made <jats:italic>r<\/jats:italic>-partite by deleting <jats:inline-formula><jats:alternatives><jats:tex-math>$$o(n^{2})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges. Here we consider a natural variant of this\u2014the minimum degree stability of <jats:italic>H<\/jats:italic>-free graphs. In particular, what is the least <jats:italic>c<\/jats:italic> such that any <jats:italic>n<\/jats:italic>-vertex <jats:italic>H<\/jats:italic>-free graph with minimum degree greater than <jats:italic>cn<\/jats:italic> can be made <jats:italic>r<\/jats:italic>-partite by deleting <jats:inline-formula><jats:alternatives><jats:tex-math>$$o(n^{2})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges? We determine this least value for all 3-chromatic <jats:italic>H<\/jats:italic> and for very many non-3-colourable <jats:italic>H<\/jats:italic> (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andr\u00e1sfai-Erd\u0151s-S\u00f3s theorem and work of Alon and Sudakov.<\/jats:p>","DOI":"10.1007\/s00493-023-00010-1","type":"journal-article","created":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T08:02:27Z","timestamp":1683878547000},"page":"129-147","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Minimum Degree Stability of H-Free Graphs"],"prefix":"10.1007","volume":"43","author":[{"given":"Freddie","family":"Illingworth","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,12]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Allen, P.: Dense $$H$$-free graphs are almost $$(\\chi (H)-1)$$-partite. Electron. J. Comb. 17(1.21) (2010)","DOI":"10.37236\/293"},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1002\/rsa.20708","volume":"51","author":"P Allen","year":"2017","unstructured":"Allen, P., B\u00f6ttcher, J., Griffiths, S., Kohayakawa, Y., Morris, R.: Chromatic thresholds in dense random graphs. Random Struct. Algorithms 51(2), 185\u2013214 (2017)","journal-title":"Random Struct. Algorithms"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Sudakov, B.: $$H$$-free graphs of large minimum degree. Electron. J. Combin. 13(1.19) (2006)","DOI":"10.37236\/1045"},{"issue":"3","key":"10_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90133-2","volume":"8","author":"B Andr\u00e1sfai","year":"1974","unstructured":"Andr\u00e1sfai, B., Erd\u0151s, P., S\u00f3s, V.T.: On the connection between chromatic number, maximal clique and minimal degree of a graph. Discret. Math. 8(3), 205\u2013218 (1974)","journal-title":"Discret. Math."},{"issue":"3","key":"10_CR5","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1017\/S0963548399003831","volume":"8","author":"S Brandt","year":"1999","unstructured":"Brandt, S.: On the structure of dense triangle-free graphs. Combin. Probab. Comput. 8(3), 237\u2013245 (1999)","journal-title":"Combin. Probab. Comput."},{"key":"10_CR6","unstructured":"Brandt, S., Thomass\u00e9, S.: Dense Triangle-Free Graphs are Four-Colorable: A Solution to the Erd\u0151s-Simonovits Problem (2005). Available at http:\/\/perso.ens-lyon.fr\/stephan.thomasse\/"},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1017\/S0963548397003167","volume":"6","author":"CC Chen","year":"1997","unstructured":"Chen, C.C., Jin, G.P., Koh, K.M.: Triangle-free graphs with large degree. Combin. Probab. Comput. 6(4), 381\u2013396 (1997)","journal-title":"Combin. Probab. Comput."},{"issue":"3","key":"10_CR8","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02759942","volume":"2","author":"P Erd\u0151s","year":"1964","unstructured":"Erd\u0151s, P.: On extremal problems of graphs and generalized graphs. Israel J. Math. 2(3), 183\u2013190 (1964)","journal-title":"Israel J. Math."},{"key":"10_CR9","unstructured":"Erd\u0151s, P.: Some recent results on extremal problems in graph theory. In: Theory of Graphs (International Symposium, Rome, 1966), pp. 117\u2013123. Gordon and Breach, New York (1967)"},{"key":"10_CR10","unstructured":"Erd\u0151s, P.: On some new inequalities concerning extremal properties of graphs. In: Theory of Graphs (Proceedings of Colloquium, Tihany, 1966), pp. 77\u201381. Academic Press, New York (1968)"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0012-365X(73)90126-X","volume":"5","author":"P Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Simonovits, M.: On a valence problem in extremal graph theory. Discret. Math. 5(4), 323\u2013334 (1973)","journal-title":"Discret. Math."},{"issue":"4","key":"10_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/jgt.20505","volume":"66","author":"W Goddard","year":"2010","unstructured":"Goddard, W., Lyle, J.: Dense graphs with small clique number. J. Gr. Theory 66(4), 319\u2013331 (2010)","journal-title":"J. Gr. Theory"},{"key":"10_CR13","first-page":"89","volume":"13","author":"R H\u00e4ggkvist","year":"1982","unstructured":"H\u00e4ggkvist, R.: Odd cycles of specified length in non-bipartite graphs. Ann. Discret. Math. 13, 89\u201399 (1982)","journal-title":"Ann. Discret. Math."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Illingworth, F.: The chromatic profile of locally colourable graphs. Combin. Probab. Comput. 31, 976\u20131009 (2022)","DOI":"10.1017\/S0963548322000050"},{"issue":"1","key":"10_CR15","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0012-365X(94)00063-O","volume":"145","author":"GP Jin","year":"1995","unstructured":"Jin, G.P.: Triangle-free four-chromatic graphs. Discret. Math. 145(1), 151\u2013170 (1995)","journal-title":"Discret. Math."},{"key":"10_CR16","unstructured":"Koml\u00f3s, J., Simonovits, M.: Szemer\u00e9di\u2019s regularity lemma and its applications in graph theory. In: Combinatorics. Paul Erd\u0151s is Eighty, Volume 2, number 2 in Bolyai Society Mathematical Studies, pp. 295\u2013352. J\u00e1nos Bolyai Mathematical Society, Budapest (1996)"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"K\u0151v\u00e1ri, T., S\u00f3s, V., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloq. Math. 3(1), 50\u201357 (1954)","DOI":"10.4064\/cm-3-1-50-57"},{"issue":"4","key":"10_CR18","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00493-006-0028-8","volume":"26","author":"T \u0141uczak","year":"2006","unstructured":"\u0141uczak, T.: On the structure of triangle-free graphs of large minimum degree. Combinatorica 26(4), 489\u2013493 (2006)","journal-title":"Combinatorica"},{"key":"10_CR19","unstructured":"Nikiforov, V.: Chromatic number and mimimum degree of $${K}_{r}$$-free graphs, arXiv:1001.2070 (2010)"},{"key":"10_CR20","unstructured":"Simonovits, M.: A method for solving extremal problems in graph theory, stability problems. In: Theory of Graphs, pp. 279\u2013319. Academic Press, New York (1968)"},{"key":"10_CR21","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs. In: Probl\u00e8mes combinatoires et th\u00e9orie des graphes, number 260 in Colloquium International CNRS, pp. 399\u2013401. CNRS, Paris (1978)"},{"issue":"4","key":"10_CR22","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/s00493-002-0009-5","volume":"22","author":"C Thomassen","year":"2002","unstructured":"Thomassen, C.: On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica 22(4), 591\u2013596 (2002)","journal-title":"Combinatorica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00010-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00010-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00010-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T11:03:29Z","timestamp":1690887809000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00010-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00010-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2]]},"assertion":[{"value":"16 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}