Tuza's Conjecture is Asymptotically Tight for Dense Graphs

An old conjecture of Z. Tuza says that for any graph G, the ratio of the minimum size, tau(3)(G), of a set of edges meeting all triangles to the maximum size, nu(3)(G), of an edge-disjoint triangle packing is at most 2. Here, disproving a conjecture of R. Yuster, we show that for any fixed, positive a there are arbitrarily large graphs G of positive density satisfying tau(3)(G) > (1 - o(1))|G|/2 and nu(3)(G) < (1 + alpha)|G|/4.