On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth

Author(s)

Botler, F. ; Fernandes, C. G. ; Gutierrez, J.

• Document type: Journal article
• Source: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30.

Abstract

Tuza (1981) conjectured that the cardinality tau(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality nu(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; and we show that tau(G) <= 3/2 nu(G) for every planar triangulation G different from K-4; and that tau(G) <= 9/5 nu(G) + 1/5 if G is a maximal graph with treewidth 3. (AU)

• FAPESP's process: 15/08538-5 - Graph transversals
• Grantee: Juan Gabriel Gutierrez Alva
• Support Opportunities: Scholarships in Brazil - Doctorate