{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:06:33Z","timestamp":1761599193606,"version":"build-2065373602"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:00:00Z","timestamp":1760400000000},"content-version":"vor","delay-in-days":13,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Let\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$r \\ge 3$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo>\u2265<\/mml:mo>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    be fixed and\n                    <jats:italic>G<\/jats:italic>\n                    be an\n                    <jats:italic>n<\/jats:italic>\n                    -vertex graph. A long-standing conjecture of Gy\u0151ri states that if\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$e(G) = t_{r-1}(n) + k$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>e<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>G<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:msub>\n                              <mml:mi>t<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mi>r<\/mml:mi>\n                                <mml:mo>-<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msub>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$t_{r-1}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi>t<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mi>r<\/mml:mi>\n                                <mml:mo>-<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msub>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    denotes the number of edges of the Tur\u00e1n graph on\n                    <jats:italic>n<\/jats:italic>\n                    vertices and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$r - 1$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    parts, then\n                    <jats:italic>G<\/jats:italic>\n                    has at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(2 - o(1))k\/r$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mi>o<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    edge disjoint\n                    <jats:italic>r<\/jats:italic>\n                    -cliques. We prove this conjecture.\n                  <\/jats:p>","DOI":"10.1007\/s00493-025-00184-w","type":"journal-article","created":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T16:07:15Z","timestamp":1760458035000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Packing edge disjoint cliques in graphs"],"prefix":"10.1007","volume":"45","author":[{"given":"J\u00f3zsef","family":"Balogh","sequence":"first","affiliation":[]},{"given":"Michael C.","family":"Wigal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,14]]},"reference":[{"key":"184_CR1","unstructured":"Balogh, J., He, J., Krueger, R.A., Nguyen, T., Wigal, M.C.: Clique covers and decompositions of cliques of graphs, arXiv:2412.05522, (2024)"},{"issue":"2","key":"184_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1017\/S0963548320000358","volume":"30","author":"A Blumenthal","year":"2021","unstructured":"Blumenthal, A., Lidick\u00fd, B., Pehova, Y., Pfender, F., Pikhurko, O., Volec, J.: Sharp bounds for decomposing graphs into edges and triangles. Combin. Probab. Comput. 30(2), 271\u2013287 (2021)","journal-title":"Combin. Probab. Comput."},{"key":"184_CR3","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1017\/S0305004100052063","volume":"79","author":"B Bollob\u00e1s","year":"1976","unstructured":"Bollob\u00e1s, B.: On complete subgraphs of different order. Math. Proc. Cambridge Philos. Soc. 79, 19\u201324 (1976)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"1","key":"184_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0602001","volume":"2","author":"FRK Chung","year":"1981","unstructured":"Chung, F.R.K.: On the decomposition of graphs. SIAM J. Algebraic Discrete Methods 2(1), 1\u201312 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"184_CR5","unstructured":"Erd\u0151s, P.: Some unsolved problems in graph theory and combinatorial analysis, in: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London-New York, 97\u2013109, (1971)"},{"key":"184_CR6","doi-asserted-by":"publisher","first-page":"106","DOI":"10.4153\/CJM-1966-014-3","volume":"18","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Goodman, A., P\u00f3sa, L.: The representation of graphs by set intersections. Canadian J. Math. 18, 106\u2013112 (1966)","journal-title":"Canadian J. Math."},{"key":"184_CR7","unstructured":"Gy\u0151ri, E.: On the number of edge disjoint triangles in graphs of given size, in: Combinatorics (Eger, 1987), Colloq. Math. Soc. J\u00e1nos Bolyai, 52, North-Holland, Amsterdam, 267\u2013276, (1988)"},{"issue":"3","key":"184_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01205075","volume":"11","author":"E Gy\u0151ri","year":"1991","unstructured":"Gy\u0151ri, E.: On the number of edge disjoint cliques in graphs of a given size. Combinatorica 11(3), 231\u2013243 (1991)","journal-title":"Combinatorica"},{"key":"184_CR9","unstructured":"Gy\u0151ri, E.: Edge disjoint cliques in graphs, in: Sets, graphs, and numbers (Budapest 1991), Colloq. Math. Soc. J\u00e1nos Bolyai, 60, North-Holland, Amsterdam, 357\u2013363, (1992)"},{"key":"184_CR10","doi-asserted-by":"crossref","unstructured":"Gy\u0151ri, E., Keszegh, B.: On the number of edge-disjoint triangles in $$K_4$$-free graphs. Combinatorica 37(6), 1113\u20131124 (2017)","DOI":"10.1007\/s00493-016-3500-0"},{"key":"184_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF01896127","volume":"34","author":"E Gy\u0151ri","year":"1979","unstructured":"Gy\u0151ri, E., Kostochka, A.V.: On a problem of G. O. H. Katona and T. Tarj\u00e1n. Acta Math. Acad. Sci. Hungar. 34, 321\u2013327 (1979)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"184_CR12","first-page":"315","volume":"22","author":"E Gy\u0151ri","year":"1987","unstructured":"Gy\u0151ri, E., Tuza, Zs.: Decomposition of graphs into complete subgraphs of given order, Sudia Sci. Math. Hung. 22, 315\u2013320 (1987)","journal-title":"Math. Hung."},{"issue":"1","key":"184_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s004930170003","volume":"21","author":"PE Haxell","year":"2001","unstructured":"Haxell, P.E., R\u00f6dl, V.: Integer and fractional packings in dense graphs. Combinatorica 21(1), 13\u201338 (2001)","journal-title":"Combinatorica"},{"key":"184_CR14","unstructured":"Katona, G.O.H., Tarj\u00e1n, T., 5th Hungarian Combinatorial Colloquium, Open Problem. Combinatorics (Coll. Math. Soc. Bolyai, 18, Keszthely,: North-holland. Amsterdam 1978, 1207 (1976)"},{"issue":"1","key":"184_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF01848173","volume":"12","author":"J Kahn","year":"1981","unstructured":"Kahn, J.: Proof of a conjecture of katona and tarj\u00e1n. Period. Math. Hungar. 12(1), 81\u201382 (1981)","journal-title":"Period. Math. Hungar."},{"issue":"3","key":"184_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1017\/S0963548318000421","volume":"28","author":"D Kr\u00e1l\u2019","year":"2019","unstructured":"Kr\u00e1l\u2019, D., Lidick\u00fd, B., Martins, T.L., Pehova, Y.: Decomposing graphs into edges and triangles. Combin. Probab. Comput. 28(3), 465\u2013472 (2019)","journal-title":"Combin. Probab. Comput."},{"key":"184_CR17","unstructured":"Tuza, Zs.: Unsolved combinatorial problems, Part I. BRICS Lecture Series LS-01-1, (2001)"},{"key":"184_CR18","unstructured":"Wilson, R.M.: Decomposition of complete graphs into subgraphs isomorphic to a given graph, in: Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congr. Numer., No. XV, Utilitas Math, Winnipeg, MB, 647\u2013659 (1975)"},{"key":"184_CR19","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1002\/rsa.20048","volume":"26","author":"R Yuster","year":"2005","unstructured":"Yuster, R.: Integer and fractional packing of families of graphs. Random Structures and Algorithms 26, 110\u2013118 (2005)","journal-title":"Random Structures and Algorithms"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00184-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00184-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00184-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:02:33Z","timestamp":1761598953000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00184-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["184"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00184-w","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,10]]},"assertion":[{"value":"23 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"56"}}