Tuza (1981) 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 $ u(G)$ of a maximum set of edge-disjoint triangles of $G$. In this paper we present three results regarding Tuzas Conjecture. We verify it for graphs with treewidth at most $6$; we show that $tau(G)leq frac{3}{2}, u(G)$ for every planar triangulation $G$ different from $K_4$; and that $tau(G)leqfrac{9}{5}, u(G) + frac{1}{5}$ if $G$ is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that $tau(G) leq 2, u(G)$ for every $K_8$-free chordal graph $G$.
تحميل البحث