On Tuza's conjecture in co-chain graphs

Read full text
Authors: Luis Eduardo Chahua, Juan Gutiérrez
Cited by: 0

Abstract

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.

Fields of Study & Subjects

Advanced Graph Theory Research Graph theory and applications Graph Labeling and Dimension Problems

Publication details

Journal / source
Discussiones Mathematicae Graph Theory
Publication date
1 January 2026
Language
EN