{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T07:45:12Z","timestamp":1780386312516,"version":"3.54.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Umea University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>Let $$\\textbf{G}:=(G_1, G_2, G_3)$$<\/jats:tex-math>\n \n G<\/mml:mi>\n :<\/mml:mo>\n =<\/mml:mo>\n (<\/mml:mo>\n \n G<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n G<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n G<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a triple of graphs on the same vertex set V<\/jats:italic> of size n<\/jats:italic>. A rainbow triangle in $$\\textbf{G}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a triple of edges $$(e_1, e_2, e_3)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n \n e<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n e<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n e<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with $$e_i\\in G_i$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \u2208<\/mml:mo>\n \n G<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for each i<\/jats:italic> and $$\\{e_1, e_2, e_3\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n \n e<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n e<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n e<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> forming a triangle in V<\/jats:italic>. The triples $$\\textbf{G}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities $$(\\alpha _1, \\alpha _2, \\alpha _3)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n \n \u03b1<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u03b1<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u03b1<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that if $$\\vert E(G_i)\\vert > \\alpha _i n^2$$<\/jats:tex-math>\n \n \n |<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n \n G<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \n |<\/mml:mo>\n ><\/mml:mo>\n <\/mml:mrow>\n \n \u03b1<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for each i<\/jats:italic> and n<\/jats:italic> is sufficiently large, then $$\\textbf{G}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and \u0160\u00e1mal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Gy\u0151ri, He, Lv, Salia, Tompkins, Varga and Zhu.<\/jats:p>","DOI":"10.1007\/s00493-024-00102-6","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T10:01:51Z","timestamp":1714384911000},"page":"977-1010","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates"],"prefix":"10.1007","volume":"44","author":[{"given":"Victor","family":"Falgas-Ravry","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klas","family":"Markstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eero","family":"R\u00e4ty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"102_CR1","doi-asserted-by":"publisher","DOI":"10.19086\/aic.12043","author":"R Aharoni","year":"2020","unstructured":"Aharoni, R., DeVos, M., de la Maza, S., Montejano, A., \u0160\u00e1mal, R.: A rainbow version of Mantel\u2019s theorem. Adv. Comb. (2020). https:\/\/doi.org\/10.19086\/aic.12043","journal-title":"Adv. Comb."},{"issue":"3","key":"102_CR2","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. Discrete Math. 8(3), 205\u2013218 (1974)","journal-title":"Discrete Math."},{"key":"102_CR3","doi-asserted-by":"crossref","unstructured":"Babi\u0144ski, S., Grzesik, A.: Graphs without a rainbow path of length 3 (2022). Arxiv preprint arXiv:2211.02308","DOI":"10.5817\/CZ.MUNI.EUROCOMB23-011"},{"issue":"4","key":"102_CR4","doi-asserted-by":"publisher","first-page":"2416","DOI":"10.1137\/19M1253344","volume":"33","author":"J Balogh","year":"2019","unstructured":"Balogh, J., Li, L.: The typical structure of Gallai colorings and their extremal graphs. SIAM J. Discrete Math. 33(4), 2416\u20132443 (2019)","journal-title":"SIAM J. Discrete Math."},{"key":"102_CR5","doi-asserted-by":"publisher","first-page":"2143","DOI":"10.1016\/j.disc.2017.04.011","volume":"340","author":"FS Benevides","year":"2017","unstructured":"Benevides, F.S., Hoppen, C., Sampaio, R.M.: Edge-colorings of graphs avoiding complete graphs with a prescribed coloring. Discrete Math. 340, 2143\u20132160 (2017)","journal-title":"Discrete Math."},{"issue":"2","key":"102_CR6","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00493-006-0009-y","volume":"26","author":"A Bondy","year":"2006","unstructured":"Bondy, A., Shen, J., Thomass\u00e9, S., Thomassen, C.: Density conditions for triangles in multipartite graphs. Combinatorica 26(2), 121\u2013131 (2006)","journal-title":"Combinatorica"},{"issue":"1","key":"102_CR7","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1002\/(SICI)1097-0118(199709)26:1<9::AID-JGT2>3.0.CO;2-N","volume":"26","author":"K Cameron","year":"1997","unstructured":"Cameron, K., Edmonds, J.: Lambda composition. J. Graph Theory 26(1), 9\u201316 (1997)","journal-title":"J. Graph Theory"},{"issue":"1","key":"102_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/rsa.20535","volume":"47","author":"B DeMarco","year":"2015","unstructured":"DeMarco, B., Kahn, J.: Mantel\u2019s theorem for random graphs. Random Struct. Algorithms 47(1), 59\u201372 (2015)","journal-title":"Random Struct. Algorithms"},{"key":"102_CR9","unstructured":"Diwan, A., Mubayi, D.: Tur\u00e1n theorem with colors. Preprint available at http:\/\/www.math.cmu.edu\/~mubayi\/papers\/webturan.pdf (2006)"},{"key":"102_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0167-5060(08)70377-7","volume":"55","author":"P Erd\u0151s","year":"1993","unstructured":"Erd\u0151s, P., Tuza, Z.: Rainbow subgraphs in edge-colorings of complete graphs. Quo vadis graph theory. Ann. Discrete Math. 55, 81\u201388 (1993)","journal-title":"Ann. Discrete Math."},{"key":"102_CR11","unstructured":"Falgas-Ravry, V., Marstr\u00f6m, K., R\u00e4ty, E.: Rainbow variations on a theme by Mantel II: minimum degree problems for Gallai colouring templates (2022). ArXiv preprint arXiv: 2212.07180"},{"issue":"4","key":"102_CR12","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1002\/rsa.20777","volume":"54","author":"V Falgas-Ravry","year":"2019","unstructured":"Falgas-Ravry, V., O\u2019Connell, K., Uzzell, A.: Multicolor containers, extremal entropy, and counting. Random Struct. Algorithms 54(4), 676\u2013720 (2019)","journal-title":"Random Struct. Algorithms"},{"key":"102_CR13","unstructured":"Frankl, P.: Graphs without rainbow triangles (2022). ArXiv preprint arXiv:2203.07768"},{"key":"102_CR14","unstructured":"Frankl, P., Gy\u0151ri, E., He, Z., Lv, Z., Salia, N., Tompkins, C., Varga, K., Zhu, X.: Some remarks on graphs without rainbow triangles (2022). ArXiv preprint arXiv:2204.07567"},{"key":"102_CR15","doi-asserted-by":"crossref","unstructured":"Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory\u2014a dynamic survey. Theory Appl. Graphs 1, Paper 1 (2014)","DOI":"10.20429\/tag.2014.000101"},{"issue":"1","key":"102_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math. Hungar. 18(1), 25\u201366 (1967). (in German)","journal-title":"Acta Math. Hungar."},{"issue":"3","key":"102_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1002\/jgt.20001","volume":"46","author":"A Gy\u00e1rf\u00e1s","year":"2004","unstructured":"Gy\u00e1rf\u00e1s, A., Simonyi, G.: Edge colorings of complete graphs without tricolored triangles. J. Graph Theory 46(3), 211\u2013216 (2004)","journal-title":"J. Graph Theory"},{"issue":"2","key":"102_CR18","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.aam.2003.08.005","volume":"33","author":"P Keevash","year":"2004","unstructured":"Keevash, P., Saks, M., Sudakov, B., Verstra\u00ebte, J.: Multicolour Tur\u00e1n problems. Adv. Appl. Math. 33(2), 238\u2013262 (2004)","journal-title":"Adv. Appl. Math."},{"key":"102_CR19","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s004930070022","volume":"20","author":"J K\u00f6rner","year":"2000","unstructured":"K\u00f6rner, J., Simonyi, G.: Graph pairs and their entropies: modularity problems. Combinatorica 20, 227\u2013240 (2000)","journal-title":"Combinatorica"},{"issue":"1","key":"102_CR20","volume":"22","author":"C Magnant","year":"2015","unstructured":"Magnant, C.: Density of Gallai multigraphs. Electron. J. Comb. 22(1), Paper 28 (2015)","journal-title":"Electron. J. Comb."},{"key":"102_CR21","first-page":"60","volume":"10","author":"W Mantel","year":"1907","unstructured":"Mantel, W.: Problem 28 (solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff). Wiskundige Opgaven 10, 60\u201361 (1907)","journal-title":"Wiskundige Opgaven"},{"key":"102_CR22","first-page":"939","volume":"18","author":"IZ Ruzsa","year":"1978","unstructured":"Ruzsa, I.Z., Szemer\u00e9di, E.: Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, 939\u2013945 (1978)","journal-title":"Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai"},{"issue":"1","key":"102_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0012-365X(83)90273-X","volume":"46","author":"J Shearer","year":"1983","unstructured":"Shearer, J.: A note on the independence number of triangle-free graphs. Discrete Math. 46(1), 83\u201387 (1983)","journal-title":"Discrete Math."},{"issue":"4","key":"102_CR24","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-024-00102-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00102-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00102-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:08:45Z","timestamp":1728302925000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00102-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["102"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00102-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"19 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}