A generalization of Tuza's conjecture

DOI10.1002/JGT.22533MaRDI QIDQ5066897zbMATH OpenOpenAlexWikidataFDO

Authors Ron Aharoni, Shira Zerbib

Publication date 31 March 2022

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.07497

zbMATH Keywords

3-uniform hypergraphscoversmatchingsTuza's conjecture

Mathematics Subject Classification ID

Distance in graphs (05C12) Enumeration in graph theory (05C30) Hypergraphs (05C65)

Abstract: A famous conjecture of Tuza cite{tuza} is that the minimal number of edges needed to cover all triangles in a graph is at most twice the maximal number of edge-disjoint triangles. We propose a wider setting for this conjecture. For a hypergraph $H$ let $u^{(m)}(H)$ be the maximal size of a collection of edges, no two of which share $m$ or more vertices, and let $a{u}^{(m)}(H)$ be the minimal size of a collection $C$ of sets of $m$ vertices, such that every edge in $H$ contains a set from $C$. We conjecture that the maximal ratio $a{u}^{(m)}(H)/u^{(m)}(H)$ is attained in hypergraphs for which $u^{(m)}(H)=1$. This would imply, in particular, the following generalization of Tuza's conjecture: if $H$ is $3$-uniform, then $a{u}^{(2)}(H)/u^{(2)}(H)le2$. (Tuza's conjecture is the case in which $H$ is the set of all triples of vertices of triangles in the graph). We show that most known results on Tuza's conjecture go over to this more general setting. We also prove some general results on the ratio $a{u}^{(m)}(H)/u^{(m)}(H)$, and study the fractional versions and the case of $k$-partite hypergraphs.

Recommendations

• Improved bounds on a generalization of Tuza's conjecture
• Packing and covering triangles in tripartite graphs
• On a conjecture of Tuza about packing and covering of triangles
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Tuza's conjecture for random graphs

Cited in

(18)

• Packing and covering triangles in tripartite graphs
• A generalization of Erdős' matching conjecture
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• Improved bounds on a generalization of Tuza's conjecture
• The geometry and combinatorics of discrete line segment hypergraphs
• Packing and covering tetrahedra
• The solution of the Tame Generators Conjecture according to Shestakov and Umirbaev
• Large triangle packings and Tuza's conjecture in sparse random graphs
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• A Turán-type generalization of Tuza's triangle edge cover problem
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• A Possible Generalization of Maeda’s Conjecture
• An asymptotic resolution of a conjecture of Szemerédi and Petruska
• Tuza's conjecture for binary geometries
• Generalized Tuza's conjecture for random hypergraphs
• Approximate hypergraph vertex cover and generalized Tuza's conjecture
• New bounds on a generalization of Tuza's conjecture
• A note on the Tu-Deng conjecture

This page was built for publication: A generalization of Tuza's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066897)