Tuza's Conjecture for Graphs of Maximum Average Degree Less Than 7
classification
🧮 math.CO
keywords
conjecturetuzagraphsaveragedegreeintroduceonig--egervtriangles
read the original 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\"onig--Egerv\'ary graphs, a generalization of the well-studied K\"onig--Egerv\'ary graphs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.