{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:20Z","timestamp":1787321120404,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Nucleo Milenio Informacion y Coordinacion en Redes ICM\/FIC","award":["RC130003"],"award-info":[{"award-number":["RC130003"]}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["11150913"],"award-info":[{"award-number":["11150913"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["11170931"],"award-info":[{"award-number":["11170931"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Given integers $r, k \\geq2$ let $\\kappa_{r,k+1}(G)$ denote the number of distinct edge colorings of $G$ with $r$ colors, which are $K_{k+1}$-free, i.e., which contain no monochromatic clique on $k+1$ vertices. Alon et al. [ J. Lond. Math. Soc. (2), 70 (2004), pp. 273--288] show that for $r\\in\\{2,3\\}$ and all $k\\geq 2$ the maximum of $\\kappa_{r,k+1}(G)$ over all $G$ on $n$ vertices is achieved only by the Tur\u00e1n graph, provided $n&gt;n_0(k)$ is sufficiently large. The proof uses Szemer\u00e9di's regularity lemma and yields an $n_0(k)$ which is tower type with height exponential in $k$. As a lower bound the authors observed that $n_0(k)$ must be at least exponential in $k$. In this paper we essentially close the gap between the upper and the lower bound for $n_0(k)$. Answering the question posed by Alon et al. we show that the lower bound is of correct order and that it suffices to choose $n_0(k)=\\exp(Ck^4)$ for some absolute constant $C$.<\/jats:p>","DOI":"10.1137\/17m1130502","type":"journal-article","created":{"date-parts":[[2018,6,14]],"date-time":"2018-06-14T12:53:05Z","timestamp":1528980785000},"page":"1364-1368","source":"Crossref","is-referenced-by-count":9,"title":["Improved Bound on the Maximum Number of Clique-Free Colorings with Two and Three Colors"],"prefix":"10.1137","volume":"32","author":[{"given":"Hi\u1ec7p","family":"H\u00e0n","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Jim\u00e9nez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1112\/S0024610704005563"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3290-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32789.x"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70608-3"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/130947878"},{"key":"atypb9","unstructured":"O. Pikhurko, K. Staden, and Z. B. Yilma,\n                      The Erdo\u0308s-Rothschild problem on edge-colourings with forbidden monochromatic cliques\n                      , Math. Proc Cambridge Philos. Soc., to appear."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdr031"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"atypb12","first-page":"436","volume":"48","author":"Tura\u0301n P.","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199604)21:4<441::AID-JGT10>3.0.CO;2-I"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1130502","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:16Z","timestamp":1787317576000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1130502"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1130502"],"URL":"https:\/\/doi.org\/10.1137\/17m1130502","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}