On Tuza's conjecture in dense graphs

Luis Chahua, Juan Gutiérrez

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

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.

Idioma originalInglés
Páginas (desde-hasta)225-233
Número de páginas9
PublicaciónDiscrete Applied Mathematics
Volumen377
DOI
EstadoPublicada - 31 dic. 2025

Huella

Profundice en los temas de investigación de 'On Tuza's conjecture in dense graphs'. En conjunto forman una huella única.

Citar esto