{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T14:38:42Z","timestamp":1767969522325,"version":"3.49.0"},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,6,5]],"date-time":"2020-06-05T00:00:00Z","timestamp":1591315200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function <jats:italic>L<\/jats:italic> = <jats:italic>L<\/jats:italic>(<jats:italic>r,\u025b<\/jats:italic>) such that every <jats:italic>K<jats:sub>r<\/jats:sub><\/jats:italic>-free graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices with minimum degree at least ((2<jats:italic>r<\/jats:italic>\u20135)\/(2<jats:italic>r<\/jats:italic>\u20133)+<jats:italic>\u025b<\/jats:italic>)<jats:italic>n<\/jats:italic> is homomorphic to a <jats:italic>K<jats:sub>r<\/jats:sub><\/jats:italic>-free graph on at most <jats:italic>L<\/jats:italic> vertices. It is known that the required minimum degree condition is approximately best possible for this result.<\/jats:p><jats:p>For <jats:italic>r<\/jats:italic> = 3 this result was obtained by \u0141uczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from \u0141uczak\u2019s result. \u0141uczak\u2019s proof was based on an application of Szemer\u00e9di\u2019s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on <jats:italic>L<\/jats:italic>(3, <jats:italic>\u025b<\/jats:italic>). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for <jats:italic>L<\/jats:italic>(<jats:italic>r<\/jats:italic>, <jats:italic>\u025b<\/jats:italic>) that is doubly exponential in poly(<jats:italic>\u025b<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548319000324","type":"journal-article","created":{"date-parts":[[2020,6,5]],"date-time":"2020-06-05T07:10:27Z","timestamp":1591341027000},"page":"641-649","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["On the structure of Dense graphs with bounded clique number"],"prefix":"10.1017","volume":"29","author":[{"given":"Heiner","family":"Oberkampf","sequence":"first","affiliation":[]},{"given":"Mathias","family":"Schacht","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,6,5]]},"reference":[{"key":"S0963548319000324_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22369"},{"key":"S0963548319000324_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0054-1"},{"key":"S0963548319000324_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-002-0009-5"},{"key":"S0963548319000324_ref17","first-page":"436","article-title":"Eine Extremalaufgabe aus der Graphentheorie","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548319000324_ref12","unstructured":"[12] \u0141uczak, T. and Thomass\u00e9, S. Coloring dense graphs via VC-dimension. Submitted."},{"key":"S0963548319000324_ref14","unstructured":"[14] Szemer\u00e9di, E. (1978) Regular partitions of graphs. In Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399\u2013401 (English, with French summary)."},{"key":"S0963548319000324_ref13","unstructured":"[13] Nikiforov, V. Chromatic number and minimum degree of Kr -free graphs. Preprint."},{"key":"S0963548319000324_ref4","unstructured":"[4] Ebsen, O. and Schacht, M. (2017) Homomorphism thresholds for odd cycles. Combinatorica, to appear."},{"key":"S0963548319000324_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"},{"key":"S0963548319000324_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20505"},{"key":"S0963548319000324_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548319000324_ref8","unstructured":"[8] H\u00e4ggkvist, R. (1982) Odd cycles of specified length in nonbipartite graphs. In Graph Theory (Cambridge, 1981), Vol. 62 of North-Holland Mathematics Studies, North-Holland, pp. 89\u201399."},{"key":"S0963548319000324_ref3","unstructured":"[3] Brandt, S. and Thomass\u00e9, S. Dense triangle-free graphs are four-colorable: A solution to the Erd\u0151s\u2013Simonovits problem. Preprint."},{"key":"S0963548319000324_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548319000324_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90126-X"},{"key":"S0963548319000324_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0028-8"},{"key":"S0963548319000324_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.11.016"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T12:06:03Z","timestamp":1600085163000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000324\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,5]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0963548319000324"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000324","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,5]]},"assertion":[{"value":"\u00a9 Cambridge University Press 2020","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}