On Tuza's conjecture in co-chain graphs
Luis Eduardo Chahua, Juan Gutiérrez · Discussiones Mathematicae Graph Theory · 2026
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 has been proved for several important graph classes, such as planar graphs, tripartite graphs, and others.However, it remains open for other important classes of graphs, such as chordal graphs.Furthermore, it remains open for major subclasses of chordal graphs, such as split graphs and interval graphs.In this paper, we show that Tuza's conjecture is valid for co-chain graphs with an even number of vertices on both sides of the partition, a known subclass of interval graphs.