Tuza's Conjecture is Asymptotically Tight for Dense Graphs

DOI10.1017/S0963548316000067zbMath1372.05166arXiv1408.4870OpenAlexW1556797074WikidataQ122998393 ScholiaQ122998393MaRDI QIDQ5366916

Jacob D. Baron, Jeffry Kahn

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (11)

Tuza's Conjecture for Threshold Graphs ⋮ Packing and covering directed triangles ⋮ Packing and Covering a Given Directed Graph in a Directed Graph ⋮ Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process ⋮ Covering triangles in edge-weighted graphs ⋮ On Tuza's conjecture for triangulations and graphs with small treewidth ⋮ On Tuza's conjecture for triangulations and graphs with small treewidth ⋮ Sufficient Conditions for Tuza’s Conjecture on Packing and Covering Triangles ⋮ Packing and covering directed triangles asymptotically ⋮ Large triangle packings and Tuza’s conjecture in sparse random graphs ⋮ Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number

Cites Work

• Integer and fractional packings in dense graphs
• Packing and covering triangles in graphs
• Explicit Ramsey graphs and orthonormal labelings
• On a conjecture of Tuza about packing and covering of triangles
• Dense Graphs With a Large Triangle Cover Have a Large Triangle Packing
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tuza's Conjecture is Asymptotically Tight for Dense Graphs