论文标题
关于Tuza的猜想在共同链图中
On Tuza's conjecture in co-chain graphs
论文作者
论文摘要
1981年，图扎（Tuza）猜想，与图形的每个三角形相交的最小边缘的基数最多是最大边缘 - 偶发三角形三角形的基数的两倍。该猜想已被证明是几个重要的图形类别，如平面图，三方图等。但是，它在其他重要的图形类别（作为和弦图）上保持开放。此外，作为串联图和间隔图的弦图的主要子类仍将其开放。在本文中，我们表明Tuza的猜想对于在分区两侧（一个已知的间隔图子类）的共同链图有效。
In 1981, Tuza conjectured that the cardinality of a minimum set of edges that intersects every triangle of a graph is at most twice the cardinality of a maximum set of edge-disjoint triangles. This conjecture have been proved for several important graph classes, as planar graphs, tripartite graphs, among others. However, it remains open on other important classes of graphs, as chordal graphs. Furthermore, it remains open for main subclasses of chordal graphs, as split graphs and interval graphs. In this paper, we show that Tuza's conjecture is valid for co-chain graphs with even number of vertices in both sides of the partition, a known subclass of interval graphs.
