Tuza's Conjecture is Asymptotically Tight for Dense Graphs

Abstract

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 edge-disjoint triangle packing is at most 2. Here, disproving a conjecture of R. Yuster, we show that for any fixed, positive $\alpha$ 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$.

Changes in version 2: fixed typos; clarified introduction slightly; clarified discussion of "gain/loss at an edge" at the bottom of p. 13. Results unchanged. 22 pages

Cited by in corpus (4)

• Improved bounds on a generalization of Tuza's conjecture
• Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles
• Tuza's Conjecture for Threshold Graphs
• On Tuza's conjecture for triangulations and graphs with small treewidth