Article ID Journal Published Year Pages File Type
6424132 European Journal of Combinatorics 2015 19 Pages PDF
Abstract

Tuza's Conjecture states that if a graph G does not contain more than k edge-disjoint triangles, then some set of at most 2k edges meets all triangles of G. We prove Tuza's Conjecture for all graphs G having no subgraph with average degree at least 7. As a key tool in the proof, we introduce a notion of reducible sets for Tuza's Conjecture; these are substructures which cannot occur in a minimal counterexample to Tuza's Conjecture. We also introduce weak König-Egerváry graphs, a generalization of the well-studied König-Egerváry graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,