On Tuza's Conjecture in Dense Graphs
<|reference_start|>On Tuza's Conjecture in Dense Graphs: In 1982, Tuza conjectured that the size $\tau(G)$ of a minimum set of edges that intersects every triangle of a graph $G$ is at most twice the size $\nu(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 $\frac{7n}{8}$. We extend this technique to show that Tuza's conjecture is valid for split graphs with minimum degree at least $\frac{3n}{5}$; and that $\tau(G) < \frac{28}{15}\nu(G)$ for every tripartite graph with minimum degree more than $\frac{33n}{56}$. Finally, we show that $\tau(G)\leq \frac{3}{2}\nu(G)$ when $G$ is a complete 4-partite graph. Moreover, this bound is tight.<|reference_end|>
@article{chahua2024on,
    title={On Tuza's Conjecture in Dense Graphs},
    author={Luis Chahua, Juan Gutierrez},
    journal={arXiv preprint arXiv:2405.11409},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.11409},
    primaryClass={math.CO cs.DM}
}