On Tuza's conjecture for triangulations and graphs with small treewidth

Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez

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

2 Citas (Scopus)

Resumen

Tuza (1981) 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. In this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; we show that [Formula presented] for every planar triangulation G different from K4; and that [Formula presented] if G is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that τ(G)≤2ν(G) for every K8-free chordal graph G.

Idioma originalInglés
Número de artículo112281
PublicaciónDiscrete Mathematics
Volumen344
N.º4
DOI
EstadoPublicada - abr. 2021

Huella

Profundice en los temas de investigación de 'On Tuza's conjecture for triangulations and graphs with small treewidth'. En conjunto forman una huella única.

Citar esto