{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:04:56Z","timestamp":1740107096400,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T00:00:00Z","timestamp":1599609600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T00:00:00Z","timestamp":1599609600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EMMI","award":["BME FIKP-MI\/SC"],"award-info":[{"award-number":["BME FIKP-MI\/SC"]}]},{"name":"National Research, Development and Innovation Office","award":["K116769","K120706","K132696","BME NC TKP2020"],"award-info":[{"award-number":["K116769","K120706","K132696","BME NC TKP2020"]}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["TUDFO\/51757\/2019"],"award-info":[{"award-number":["TUDFO\/51757\/2019"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2020,11]]},"abstract":"Abstract<\/jats:title>An edge-coloring of the complete graph $$K_n$$<\/jats:tex-math>\n\nK<\/mml:mi>\nn<\/mml:mi>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> we call F<\/jats:italic>-caring if it leaves no F<\/jats:italic>-subgraph of $$K_n$$<\/jats:tex-math>\n\nK<\/mml:mi>\nn<\/mml:mi>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> monochromatic and at the same time every subset of |V<\/jats:italic>(F<\/jats:italic>)| vertices contains in it at least one completely multicolored version of F<\/jats:italic>. For the first two meaningful cases, when $$F=K_{1,3}$$<\/jats:tex-math>\n\nF<\/mml:mi>\n=<\/mml:mo>\n\nK<\/mml:mi>\n\n1<\/mml:mn>\n,<\/mml:mo>\n3<\/mml:mn>\n<\/mml:mrow>\n<\/mml:msub>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$F=P_4$$<\/jats:tex-math>\n\nF<\/mml:mi>\n=<\/mml:mo>\n\nP<\/mml:mi>\n4<\/mml:mn>\n<\/mml:msub>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> we determine for infinitely many n<\/jats:italic> the minimum number of colors needed for an F<\/jats:italic>-caring edge-coloring of $$K_n$$<\/jats:tex-math>\n\nK<\/mml:mi>\nn<\/mml:mi>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>. An explicit family of $$2\\lceil \\log _2 n\\rceil $$<\/jats:tex-math>\n\n2<\/mml:mn>\n\u2308<\/mml:mo>\n\nlog<\/mml:mo>\n2<\/mml:mn>\n<\/mml:msub>\nn<\/mml:mi>\n\u2309<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> 3-edge-colorings of $$K_n$$<\/jats:tex-math>\n\nK<\/mml:mi>\nn<\/mml:mi>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> so that every quadruple of its vertices contains a totally multicolored $$P_4$$<\/jats:tex-math>\n\nP<\/mml:mi>\n4<\/mml:mn>\n<\/mml:msub>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> in at least one of them is also presented. Investigating related Ramsey-type problems we also show that the Shannon (OR-)capacity of the Gr\u00f6tzsch graph is strictly larger than that of the cycle of length 5.<\/jats:p>","DOI":"10.1007\/s00373-020-02214-4","type":"journal-article","created":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T14:32:09Z","timestamp":1599748329000},"page":"1623-1637","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Colorful Edge Triples in Edge-Colored Complete Graphs"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0270-4565","authenticated-orcid":false,"given":"G\u00e1bor","family":"Simonyi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,9]]},"reference":[{"key":"2214_CR1","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1017\/S0963548300004375","volume":"9","author":"N Alon","year":"2000","unstructured":"Alon, N., K\u00f6rner, J., Monti, A.: String quartets in binary. Combin. Probab. Comput. 9, 381\u2013390 (2000)","journal-title":"Combin. Probab. Comput."},{"key":"2214_CR2","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1109\/18.412676","volume":"41","author":"N Alon","year":"1995","unstructured":"Alon, N., Orlitsky, A.: Repeated communication and Ramsey graphs. IEEE Trans. Inf. Theory 41, 1276\u20131289 (1995)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"2214_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jctb.1999.1948","volume":"79","author":"M Axenovich","year":"2000","unstructured":"Axenovich, M., F\u00fcredi, Z., Mubayi, D.: On generalized Ramsey theory: the bipartite case. J. Combin. Theory Ser. B 79(1), 66\u201386 (2000)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"20","key":"2214_CR4","doi-asserted-by":"publisher","first-page":"4710","DOI":"10.1016\/j.disc.2007.08.092","volume":"308","author":"M Axenovich","year":"2008","unstructured":"Axenovich, M., Iverson, P.: Edge-colorings avoiding rainbow and monochromatic subgraphs. Discrete Math. 308(20), 4710\u20134723 (2008)","journal-title":"Discrete Math."},{"issue":"1","key":"2214_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.2000.2016","volume":"82","author":"A Blokhuis","year":"2001","unstructured":"Blokhuis, A., Faudree, R., Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M.: Anti-Ramsey colorings in several rounds. J. Combin. Theory Ser. B 82(1), 1\u201318 (2001)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2214_CR6","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TIT.2002.808128","volume":"49","author":"T Bohman","year":"2003","unstructured":"Bohman, T., Holzman, R.: A nontrivial lower bound on the Shannon capacities of the complements of odd cycles. IEEE Trans. Inf. Theory 49, 721\u2013722 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2214_CR7","first-page":"3","volume-title":"Handbook of Combinatorics","author":"JA Bondy","year":"1995","unstructured":"Bondy, J.A.: Basic graph theory: paths and circuits. In: Graham, R.R., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.) Handbook of Combinatorics, vol. 1, pp. 3\u2013110. Elsevier, Amsterdam (1995)"},{"key":"2214_CR8","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863879","volume-title":"Erd\u0151s on Graphs, His Legacy of Unsolved Problems","author":"F Chung","year":"1998","unstructured":"Chung, F., Graham, R.: Erd\u0151s on Graphs, His Legacy of Unsolved Problems. A K Peters\/CRC Press, New York (1998)"},{"issue":"16","key":"2214_CR9","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1016\/j.disc.2005.09.020","volume":"306","author":"M Cropper","year":"2006","unstructured":"Cropper, M., Gy\u00e1rf\u00e1s, A., Lehel, J.: Hall ratio of the Mycielski graphs. Discrete Math. 306(16), 1988\u20131990 (2006)","journal-title":"Discrete Math."},{"key":"2214_CR10","doi-asserted-by":"publisher","first-page":"1658","DOI":"10.1109\/ISIT.2017.8006811","volume":"2017","author":"M Dalai","year":"2017","unstructured":"Dalai, M., Guruswami, V., Radhakrishnan, J.: An improved bound on the zero-error list-decoding capacity of the 4\/3 channel. Proc. IEEE international symposium on information theory. ISIT 2017, 1658\u20131662 (2017). https:\/\/doi.org\/10.1109\/ISIT.2017.8006811","journal-title":"ISIT"},{"key":"2214_CR11","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1109\/18.21233","volume":"34","author":"P Elias","year":"1988","unstructured":"Elias, P.: Zero-error capacity under list decoding. IEEE Trans. Inf. Theory 34, 1070\u20131074 (1988)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2214_CR12","unstructured":"Erd\u0151s, P.: Solved and unsolved problems in combinatorics and combinatorial number theory. In: Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. I (Baton Rouge, La., 1981). Congr. Numer., vol. 32, pp. 49\u201362 (1981)"},{"issue":"4","key":"2214_CR13","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01195000","volume":"17","author":"P Erd\u0151s","year":"1997","unstructured":"Erd\u0151s, P., Gy\u00e1rf\u00e1s, A.: A variant of the classical Ramsey problem. Combinatorica 17(4), 459\u2013467 (1997)","journal-title":"Combinatorica"},{"key":"2214_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.2140\/pjm.1971.37.45","volume":"37","author":"P Erd\u0151s","year":"1971","unstructured":"Erd\u0151s, P., McEliece, R.J., Taylor, H.: Ramsey bounds for graph products. Pac. J. Math. 37, 45\u201346 (1971)","journal-title":"Pac. J. Math."},{"issue":"1","key":"2214_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/0605009","volume":"5","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J.: On the size of separating systems and families of perfect hash functions. SIAM J. Algebr. Discrete Methods 5(1), 61\u201368 (1984)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"2214_CR16","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0097-3165(92)90016-N","volume":"61","author":"L Gargano","year":"1992","unstructured":"Gargano, L., K\u00f6rner, J., Vaccaro, U.: Qualitative independence and Sperner problems for directed graphs. J. Combin. Theory Ser. A 61, 173\u2013192 (1992)","journal-title":"J. Combin. Theory Ser. A"},{"key":"2214_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(72)90091-X","volume":"3","author":"H Hanani","year":"1972","unstructured":"Hanani, H., Ray-Chaudhury, D.K., Wilson, R.M.: On resolvable designs. Discrete Math. 3, 343\u2013357 (1972)","journal-title":"Discrete Math."},{"key":"2214_CR18","doi-asserted-by":"publisher","first-page":"2415","DOI":"10.1007\/s00373-016-1715-x","volume":"32","author":"Z Helle","year":"2016","unstructured":"Helle, Z., Simonyi, G.: Orientations making k-cycles cyclic. Graphs Combin. 32, 2415\u20132423 (2016)","journal-title":"Graphs Combin."},{"issue":"4","key":"2214_CR19","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0607062","volume":"7","author":"J K\u00f6rner","year":"1986","unstructured":"K\u00f6rner, J.: Fredman-Koml\u00f3s bounds and information theory. SIAM J. Algebr. Discrete Methods 7(4), 560\u2013570 (1986)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"6","key":"2214_CR20","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1016\/S0195-6698(88)80048-9","volume":"9","author":"J K\u00f6rner","year":"1988","unstructured":"K\u00f6rner, J., Marton, K.: New bounds for perfect hashing via information theory. Eur. J. Combin. 9(6), 523\u2013530 (1988)","journal-title":"Eur. J. Combin."},{"key":"2214_CR21","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/0401035","volume":"1","author":"J K\u00f6rner","year":"1988","unstructured":"K\u00f6rner, J., Simonyi, G.: Separating partition systems and very different sequences. SIAM J. Discrete Math. 1, 355\u2013359 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"2214_CR22","unstructured":"K\u00f6rner, J., Simonyi, G.: Trifference. Studia Sci. Math. Hungar. 30, 95\u2013103 (1995), and also in: \u201dCombinatorics and its Applications to the Regularity and Irregularity of Structures\u201d, Walter A. Deuber and Vera T. S\u00f3s eds., Akad\u00e9miai Kiad\u00f3, Budapest (1995)"},{"issue":"3","key":"2214_CR23","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25(3), 319\u2013324 (1978)","journal-title":"J. Combin. Theory Ser. A"},{"key":"2214_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of graphs. IEEE Trans. Inf. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"2214_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00493-004-0019-6","volume":"24","author":"D Mubayi","year":"2004","unstructured":"Mubayi, D.: An explicit construction for a Ramsey problem. Combinatorica 24(2), 313\u2013324 (2004)","journal-title":"Combinatorica"},{"key":"2214_CR26","doi-asserted-by":"publisher","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J Mycielski","year":"1955","unstructured":"Mycielski, J.: Sur le coloriage des graphs. (French). Colloq. Math. 3, 161\u2013162 (1955)","journal-title":"Colloq. Math."},{"issue":"1\u20133","key":"2214_CR27","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0012-365X(00)00208-9","volume":"229","author":"J Ne\u0161et\u0159il","year":"2001","unstructured":"Ne\u0161et\u0159il, J., Rosenfeld, M.: I. Schur, C. E. Shannon and Ramsey numbers. Discrete Math. 229(1\u20133), 185\u2013195 (2001)","journal-title":"Discrete Math."},{"key":"2214_CR28","doi-asserted-by":"crossref","unstructured":"Ray-Chaudhury, D.K., Wilson, R.M.: The existence of resolvable block designs, Survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). North-Holland, Amsterdam, pp. 361\u2013375 (1973)","DOI":"10.1016\/B978-0-7204-2262-7.50035-1"},{"key":"2214_CR29","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1006\/eujc.1998.0256","volume":"20","author":"A Sali","year":"1999","unstructured":"Sali, A., Simonyi, G.: Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities. Eur. J. Combin. 20, 93\u201399 (1999)","journal-title":"Eur. J. Combin."},{"key":"2214_CR30","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","volume":"2","author":"CE Shannon","year":"1956","unstructured":"Shannon, C.E.: The zero-error capacity of a noisy channel. IRE Trans. Inf. Theory 2, 8\u201319 (1956)","journal-title":"IRE Trans. Inf. Theory"},{"issue":"1\u20133","key":"2214_CR31","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0012-365X(91)90294-C","volume":"92","author":"DR Stinson","year":"1991","unstructured":"Stinson, D.R.: A survey of Kirkman triple systems and related designs. Discrete Math. 92(1\u20133), 371\u2013393 (1991)","journal-title":"Discrete Math."},{"key":"2214_CR32","doi-asserted-by":"publisher","first-page":"R35","DOI":"10.37236\/1788","volume":"11","author":"X Xiaodong","year":"2004","unstructured":"Xiaodong, X., Zheng, X., Exoo, G., Radziszowski, S.P.: Constructive lower bounds on classical multicolor Ramsey numbers. Electron. J. Combin. 11, R35 (2004)","journal-title":"Electron. J. Combin."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02214-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-020-02214-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02214-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T23:38:53Z","timestamp":1631144333000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-020-02214-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,9]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["2214"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02214-4","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2020,9,9]]},"assertion":[{"value":"17 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}