Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424132 | European Journal of Combinatorics | 2015 | 19 Pages |
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
Gregory J. Puleo,