On a conjecture of Tuza about packing and covering of triangles

DOI10.1016/0012-365X(93)00228-WzbMath0920.05056OpenAlexW1969037852WikidataQ123025248 ScholiaQ123025248MaRDI QIDQ1896363

Michael Krivelevich

Publication date: 27 August 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(93)00228-w

zbMATH Keywords

coveringpackingtrianglesconjecture of Tuza

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of packing and covering (05B40)

Related Items (38)

Dense Graphs With a Large Triangle Cover Have a Large Triangle Packing ⋮ Induced cycles in triangle graphs ⋮ Monochromatic Clique Decompositions of Graphs ⋮ A semidefinite approach to the $K_i$-cover problem ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ The geometry and combinatorics of discrete line segment hypergraphs ⋮ Fractional \(K_{4}\)-covers ⋮ Packing and covering tetrahedra ⋮ Packing and covering triangles in \(K_{4}\)-free planar graphs ⋮ Small edge sets meeting all triangles of a graph ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Tuza's Conjecture for Threshold Graphs ⋮ Packing and covering directed triangles ⋮ A stability theorem on fractional covering of triangles by edges ⋮ Total Dual Integrality of Triangle Covering ⋮ Packing and Covering a Given Directed Graph in a Directed Graph ⋮ A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams ⋮ Kernelization for cycle transversal problems ⋮ Tuza's Conjecture is Asymptotically Tight for Dense Graphs ⋮ Edge-disjoint odd cycles in planar graphs. ⋮ Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process ⋮ Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture ⋮ Monochromatic K_r‐Decompositions of Graphs ⋮ Packing and covering triangles in planar graphs ⋮ Covering triangles in edge-weighted graphs ⋮ New kernels for several problems on planar 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 ⋮ Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal ⋮ Packing and covering directed triangles asymptotically ⋮ Large triangle packings and Tuza’s conjecture in sparse random graphs ⋮ Unnamed Item ⋮ Triangle packing and covering in dense random graphs ⋮ Packing and covering triangles in graphs ⋮ Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number ⋮ Improved bounds on a generalization of Tuza's conjecture ⋮ Tuza's conjecture for graphs with maximum average degree less than 7

Cites Work

• An approach to the subgraph homeomorphism problem
• Maximum degree and fractional matchings in uniform hypergraphs
• Matchings and covers in hypergraphs
• A conjecture on triangles of graphs
• A note on primitive skew curves

This page was built for publication: On a conjecture of Tuza about packing and covering of triangles