pith. sign in

arxiv: 1308.2211 · v3 · pith:E6EUP7RLnew · submitted 2013-08-09 · 🧮 math.CO

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

classification 🧮 math.CO
keywords conjecturetuzagraphsaveragedegreeintroduceonig--egervtriangles
0
0 comments X
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.