Tuza's Conjecture for Graphs of Maximum Average Degree Less Than 7

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.

26 pages, 11 figures. Updated with journal reference and some revisions (corrected a few minor errors, added some more background material)

References in corpus (1)

• Induced cycles in triangle graphs

Cited by in corpus (6)

• An Introduction to the Discharging Method via Graph Coloring
• Maximal $k$-Edge-Colorable Subgraphs, Vizing's Theorem, and Tuza's Conjecture
• Tuza's Conjecture for Threshold Graphs
• Induced cycles in triangle graphs
• Favaron's Theorem, k-dependence, and Tuza's Conjecture
• On Tuza's conjecture for triangulations and graphs with small treewidth