{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T06:33:25Z","timestamp":1764570805155},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>We prove the following 30 year-old conjecture of Gy\u0151ri and Tuza: the edges of every <jats:italic>n<\/jats:italic>-vertex graph <jats:italic>G<\/jats:italic> can be decomposed into complete graphs <jats:italic>C<\/jats:italic><jats:sub>1<\/jats:sub>,.\u00a0.\u00a0.,<jats:italic>C<\/jats:italic><jats:sub>\u2113<\/jats:sub> of orders two and three such that |<jats:italic>C<\/jats:italic><jats:sub>1<\/jats:sub>|+\u00b7\u00b7\u00b7+|<jats:italic>C<\/jats:italic><jats:sub>\u2113<\/jats:sub>| \u2264 (1\/2+<jats:italic>o<\/jats:italic>(1))<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>. This result implies the asymptotic version of the old result of Erd\u0151s, Goodman and P\u00f3sa that asserts the existence of such a decomposition with \u2113 \u2264 <jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>\/4.<\/jats:p>","DOI":"10.1017\/s0963548318000421","type":"journal-article","created":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T08:34:46Z","timestamp":1552466086000},"page":"465-472","source":"Crossref","is-referenced-by-count":6,"title":["Decomposing Graphs into Edges and Triangles"],"prefix":"10.1017","volume":"28","author":[{"given":"DANIEL","family":"KR\u00c1L'","sequence":"first","affiliation":[]},{"given":"BERNARD","family":"LIDICK\u00dd","sequence":"additional","affiliation":[]},{"given":"TA\u00cdSA L.","family":"MARTINS","sequence":"additional","affiliation":[]},{"given":"YANITSA","family":"PEHOVA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"S0963548318000421_ref35","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20048"},{"key":"S0963548318000421_ref30","unstructured":"Lidick\u00fd B. and Pfender F. (2017) Semidefinite programming and Ramsey numbers. arXiv:1704.03592"},{"key":"S0963548318000421_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/130926997"},{"key":"S0963548318000421_ref26","unstructured":"Kr\u00e1l' D. , Lidick\u00fd B. , Martins T. L. and Pehova Y. (2017) Decomposing graphs into edges and triangles. arXiv 1710.08486v2"},{"key":"S0963548318000421_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.02.003"},{"key":"S0963548318000421_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/130926614"},{"key":"S0963548318000421_ref34","unstructured":"Tuza Z. (2001) Unsolved Combinatorial Problems, Part I. BRICS Lecture Series LS-01-1."},{"key":"S0963548318000421_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000820"},{"key":"S0963548318000421_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.04.002"},{"key":"S0963548318000421_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/0602001"},{"key":"S0963548318000421_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000107"},{"key":"S0963548318000421_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-013-0216-9"},{"key":"S0963548318000421_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000222"},{"key":"S0963548318000421_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-015-1267-4"},{"key":"S0963548318000421_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2017.07.007"},{"key":"S0963548318000421_ref11","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-014-3"},{"key":"S0963548318000421_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.05.002"},{"key":"S0963548318000421_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1475-4"},{"key":"S0963548318000421_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.003"},{"key":"S0963548318000421_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"S0963548318000421_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22041"},{"key":"S0963548318000421_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01212981"},{"key":"S0963548318000421_ref33","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548318000421_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01848173"},{"key":"S0963548318000421_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-2662-5"},{"key":"S0963548318000421_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.08.006"},{"key":"S0963548318000421_ref16","unstructured":"Goaoc X. , Hubard A. , de Joannis de Verclos R. , Sereni J.-S. and Volec J. (2015) Limits of order types. In 31st International Symposium on Computational Geometry, Vol. 34 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, pp. 300\u2013314."},{"key":"S0963548318000421_ref17","unstructured":"Gy\u0151ri E. and Keszegh B. (2015) On the number of edge-disjoint triangles in K 4-free graphs. arXiv:1506.03306"},{"key":"S0963548318000421_ref25","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7411"},{"key":"S0963548318000421_ref20","first-page":"315","article-title":"Decompositions of graphs into complete subgraphs of given order","volume":"22","author":"Gy\u0151ri","year":"1987","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548318000421_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01896127"},{"key":"S0963548318000421_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22044"},{"key":"S0963548318000421_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9419-3"},{"key":"S0963548318000421_ref27","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000612"},{"key":"S0963548318000421_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180412"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T23:37:24Z","timestamp":1555025844000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000421\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000421"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000421","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,13]]}}}