On Tuza's Conjecture in Dense Graphs

In 1982, Tuza conjectured that the size τ(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the size ν(G) of a maximum set of edge-disjoint triangles of G. This conjecture was proved for several graph classes. In this paper, we present three results regarding Tuza's Conjecture for dense graphs. By using a probabilistic argument, Tuza proved its conjecture for graphs on n vertices with minimum degree at least 7n/8. We extend this technique to show that Tuza's conjecture is valid for split graphs with minimum degree at least 3n/5; and that τ(G) < 28/15ν(G) for every tripartite graph with minimum degree more than 33n/56. Finally, we show that τ(G)≤ 3/2ν(G) when G is a complete 4-partite graph. Moreover, this bound is tight.