Tuza's Conjecture is Asymptotically Tight for Dense Graphs

Jacob D. Baron, Jeff Kahn

An old conjecture of Zs. 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 edg…