On Tuza’s conjecture for triangulations and graphs with small treewidth
2021
Abstract 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 τ ( G ) ≤ 3 2 ν ( G ) for every planar triangulation G different from K 4 ; and that τ ( G ) ≤ 9 5 ν ( G ) + 1 5 if G is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that τ ( G ) ≤ 2 ν ( G ) for every K 8 -free chordal graph G .
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
1
Citations
NaN
KQI