{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T11:58:31Z","timestamp":1772366311847,"version":"3.50.1"},"reference-count":7,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2012,9,27]],"date-time":"2012-09-27T00:00:00Z","timestamp":1348704000000},"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":[[2012,11]]},"abstract":"<jats:p>It is well known that a graph with <jats:italic>m<\/jats:italic> edges can be made triangle-free by removing (slightly less than) <jats:italic>m<\/jats:italic>\/2 edges. On the other hand, there are many classes of graphs which are hard to make triangle-free, in the sense that it is <jats:italic>necessary<\/jats:italic> to remove roughly <jats:italic>m<\/jats:italic>\/2 edges in order to eliminate all triangles.<\/jats:p><jats:p>We prove that dense graphs that are hard to make triangle-free have a large packing of pairwise edge-disjoint triangles. In particular, they have more than <jats:italic>m<\/jats:italic>(1\/4+<jats:italic>c<\/jats:italic>\u03b2) pairwise edge-disjoint triangles where \u03b2 is the density of the graph and <jats:italic>c<\/jats:italic> \u2265 <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000235_char1\"\/><\/jats:private-char> is an absolute constant. This improves upon a previous <jats:italic>m<\/jats:italic>(1\/4\u2212<jats:italic>o<\/jats:italic>(1)) bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. We conjecture that such graphs have an asymptotically optimal triangle packing of size <jats:italic>m<\/jats:italic>(1\/3\u2212<jats:italic>o<\/jats:italic>(1)).<\/jats:p><jats:p>We extend our result from triangles to larger cliques and odd cycles.<\/jats:p>","DOI":"10.1017\/s0963548312000235","type":"journal-article","created":{"date-parts":[[2012,9,28]],"date-time":"2012-09-28T04:54:16Z","timestamp":1348808056000},"page":"952-962","source":"Crossref","is-referenced-by-count":16,"title":["Dense Graphs With a Large Triangle Cover Have a Large Triangle Packing"],"prefix":"10.1017","volume":"21","author":[{"given":"RAPHAEL","family":"YUSTER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,9,27]]},"reference":[{"key":"S0963548312000235_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)00228-W"},{"key":"S0963548312000235_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"S0963548312000235_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20048"},{"key":"S0963548312000235_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261315"},{"key":"S0963548312000235_ref4","first-page":"118","volume-title":"Proc. 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization","author":"Kortsarz","year":"2008"},{"key":"S0963548312000235_ref6","first-page":"888","volume-title":"Finite and Infinite Sets: Eger, Hungary, 1981","author":"Tuza","year":"1984"},{"key":"S0963548312000235_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00183-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T17:59:36Z","timestamp":1556128776000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000235\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,27]]},"references-count":7,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["S0963548312000235"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000235","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,27]]}}}