Tuza's Conjecture is Asymptotically Tight for Dense Graphs. (14th March 2016) - BARON, JACOB D.; KAHN, JEFF
Abstract : An old conjecture of Z. Tuza says that for any graph G, the ratio of the minimum size, τ3 ( G ), of a set of edges meeting all triangles to the maximum size, ν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 α there are arbitrarily large graphs G of positive density satisfying τ3 ( G ) > (1 − o (1))| G |/2 and ν3 ( G ) < (1 + α)| G |/4.