Dense Graphs With a Large Triangle Cover Have a Large Triangle Packing

DOI10.1017/S0963548312000235zbMath1252.05103arXiv1009.0353MaRDI QIDQ3168450

Raphael Yuster

Publication date: 31 October 2012

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

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

zbMATH Keywords

triangle-free graphasymptotically optimal triangle packingTuza's conjecture for dense graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Density (toughness, etc.) (05C42)

Related Items (12)

Monochromatic Clique Decompositions of Graphs ⋮ Fractional \(K_{4}\)-covers ⋮ Packing and covering directed triangles ⋮ Packing and Covering a Given Directed Graph in a Directed Graph ⋮ Tuza's Conjecture is Asymptotically Tight for Dense Graphs ⋮ Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process ⋮ Monochromatic K_r‐Decompositions of Graphs ⋮ Packing and covering directed triangles asymptotically ⋮ Large triangle packings and Tuza’s conjecture in sparse random graphs ⋮ Triangle packing and covering in dense random graphs ⋮ Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number ⋮ Tuza's conjecture for graphs with maximum average degree less than 7

Cites Work

• Integer and fractional packings in dense graphs
• Packing and covering triangles in graphs
• On a conjecture of Tuza about packing and covering of triangles
• Bipartite subgraphs
• Integer and fractional packing of families of graphs

This page was built for publication: Dense Graphs With a Large Triangle Cover Have a Large Triangle Packing