On Tuza's conjecture in dense graphs

Chahua L.; Gutiérrez J. · Discrete Applied Mathematics (2025) · DOI: 10.1016/j.dam.2025.06.049

Resumen

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 but it remains open even for split graphs. In this paper, we show Tuza's conjecture for split graphs with minimum degree at least [Formula presented]. We also show that τ(G)<[Formula presented], and that τ(G)≤[Formula presented]ν(G) when G is a complete 4-partite graph. Moreover, this bound is tight.

Instituciones: Universidad de Ingeniería y Tecnología