论文标题
关于Tuza的猜想，用于三角形和图形的小树宽
On Tuza's conjecture for triangulations and graphs with small treewidth
论文作者
论文摘要
Tuza（1981）猜想，与图$ g $的每个三角形相交的最小边缘的尺寸$τ（g）$最多是最大$ g $的最大边缘disschingles triangles的大小$ν（g）$的两倍。在本文中，我们提出了有关图扎的猜想的三个结果。我们将其验证为带有树宽的图形最多6美元；我们表明，$τ（g）\ leq \ frac {3} {2} \，ν（g）$ for $ k_4 $不同;并且那个$τ（g）\ leq \ frac {9} {5} \，ν（g） + \ frac {1} {5} $如果$ g $是最大图3。带有树宽的最大图3。我们的第一个结果强调了Tuza的结果，暗示了Tuza的结果，则暗示了$τ（g）$ c $ $ q leq $ q $ q. k）（k）$ - $ g $。
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)\leq \frac{3}{2}\,ν(G)$ for every planar triangulation $G$ different from $K_4$; and that $τ(G)\leq\frac{9}{5}\,ν(G) + \frac{1}{5}$ if $G$ is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that $τ(G) \leq 2\,ν(G)$ for every $K_8$-free chordal graph $G$.
