Dense graphs with a large triangle cover have a large triangle packing

Abstract

It is well known that a graph with \(m\) edges can be made triangle-free by removing (slightly less than) \(m/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 necessary to remove roughly \(m/2\) edges in order to eliminate all triangles. It is proved 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 \(m(1/4+c\beta^2)\) pairwise edge-disjoint triangles where \(\beta\) is the density of the graph and \(c\) is an absolute constant. This improves upon a previous \(m(1/4-o(1))\) bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. It is conjectured that such graphs have an asymptotically optimal triangle packing of size \(m(1/3-o(1))\). The result is extended to larger cliques and odd cycles.