{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T12:52:46Z","timestamp":1759495966600},"reference-count":17,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T00:00:00Z","timestamp":1697500800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"publisher","award":["IBS\u2010R029\u2010C1","IBS\u2010R029\u2010C4"],"award-info":[{"award-number":["IBS\u2010R029\u2010C1","IBS\u2010R029\u2010C4"]}],"id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["RS\u20102023\u201000210430"],"award-info":[{"award-number":["RS\u20102023\u201000210430"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given  graphs  over a common vertex set of size , what is the maximum value of  having no \u201ccolorful\u201d copy of , that is, a copy of  containing at most one edge from each ? Keevash, Saks, Sudakov, and Verstra\u00ebte denoted this number as  and completely determined  for large . In fact, they showed that, depending on the value of , one of the two natural constructions is always the extremal construction. Moreover, they conjectured that the same holds for every color\u2010critical graphs, and proved it for 3\u2010color\u2010critical graphs. They also asked to classify the graphs  that have only these two extremal constructions. We prove their conjecture for 4\u2010color\u2010critical graphs and for almost all \u2010color\u2010critical graphs when . Moreover, we show that for every non\u2010color\u2010critical non\u2010bipartite graphs, none of the two natural constructions is extremal for certain values of .<\/jats:p>","DOI":"10.1002\/rsa.21189","type":"journal-article","created":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T05:49:21Z","timestamp":1697608161000},"page":"460-489","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On a rainbow extremal problem for color\u2010critical graphs"],"prefix":"10.1002","volume":"64","author":[{"given":"Debsoumya","family":"Chakraborti","sequence":"first","affiliation":[{"name":"Discrete Mathematics Group (DIMAG) Institute for Basic Science (IBS)  Daejeon South Korea"}]},{"given":"Jaehoon","family":"Kim","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences KAIST  Daejeon South Korea"}]},{"given":"Hyunwoo","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences KAIST  Daejeon South Korea"}]},{"given":"Hong","family":"Liu","sequence":"additional","affiliation":[{"name":"Extremal Combinatorics and Probability Group (ECOPRO) Institute for Basic Science (IBS)  Daejeon South Korea"}]},{"given":"Jaehyeon","family":"Seo","sequence":"additional","affiliation":[{"name":"Department of Mathematics Yonsei University  Seoul South Korea"}]}],"member":"311","published-online":{"date-parts":[[2023,10,17]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.19086\/aic.12043"},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000353"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012\u2010365X(82)90115\u20107"},{"key":"e_1_2_11_5_1","doi-asserted-by":"crossref","unstructured":"D.Chakraborti J.Kim H.Lee H.Liu andJ.Seo.On a rainbow extremal problem for color\u2010critical graphs. arXiv preprint arXiv: 2204.02575 [math.CO] 2022.","DOI":"10.1002\/rsa.21189"},{"key":"e_1_2_11_6_1","unstructured":"Y.Cheng J.Han B.Wang andG.Wang.Rainbow spanning structures in graph and hypergraph systems. arXiv preprint arXiv: 2105.10219 [math.CO] 2021."},{"key":"e_1_2_11_7_1","first-page":"85","article-title":"Recherches Sur Une nouvelle esp\u00e9ce de quarr\u00e9s magiques [investigations on a new type of magic square]","volume":"9","author":"Euler L.","year":"1782","journal-title":"Verh. Zeeuwsch. Gennot. Weten. Vliss"},{"key":"e_1_2_11_8_1","unstructured":"P.Frankl.Graphs without rainbow triangles. arXiv preprint arXiv: 2203.07768 [math.CO] 2022."},{"key":"e_1_2_11_9_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12343"},{"key":"e_1_2_11_10_1","unstructured":"G.Kalai.Colorful caratheodory revisited 2009."},{"key":"e_1_2_11_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.03.009"},{"key":"e_1_2_11_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2003.08.005"},{"key":"e_1_2_11_13_1","first-page":"295","volume-title":"Combinatorics, Paul Erd\u00f6s is eighty","author":"Koml\u00f3s J.","year":"1996"},{"key":"e_1_2_11_14_1","doi-asserted-by":"publisher","DOI":"10.19086\/aic.2022.3"},{"key":"e_1_2_11_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2018.07.004"},{"key":"e_1_2_11_16_1","first-page":"279","volume-title":"Theory of graphs (Proc. Colloq., Tihany, 1966)","author":"Simonovits M.","year":"1968"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.4064\/cm\u20103\u20101\u201019\u201030"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139004114.010"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21189","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T11:39:46Z","timestamp":1706182786000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.21189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,17]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["10.1002\/rsa.21189"],"URL":"https:\/\/doi.org\/10.1002\/rsa.21189","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,17]]},"assertion":[{"value":"2023-09-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}