Packing and covering triangles in graphs
From MaRDI portal
A family of triangles in a graph \(G\) is independent if its elements are pairwise edge-disjoint. A set of edges of \(G\) is transversal for \(G\), if every triangle of \(G\) contains at least one element of the set. Denote by \(\nu(G)\) the maximum cardinality of an independent family of triangles in \(G\), and by \(\tau(G)\) the minimum cardinality of a transversal for \(G\). In this note, it is shown that for any graph \(G\), we have \(\tau(G)\leq (3-\varepsilon) \nu(G)\), where \(\varepsilon> 3/23\).
Recommendations
- Packing and covering triangles in tripartite graphs
- Packing triangles in a graph and its complement
- Packing and covering directed triangles
- Packing triangles in weighted graphs
- Packing triangles in bounded degree graphs.
- Triangle packing and covering in dense random graphs
- Packing and covering triangles in dense random graphs
- Packing triangles in low degree graphs and indifference graphs
- Packing triangles in low degree graphs and indifference graphs
Cites work
Cited in
(48)- Triangle packings and 1-factors in oriented graphs
- Brambles and independent packings in chordal graphs
- Packing and covering triangles in tripartite graphs
- Covering and independence in triangle structures
- Packing and covering triangles in \(K_{4}\)-free planar graphs
- Small edge sets meeting all triangles of a graph
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
- Packing and covering directed triangles asymptotically
- Triangle packing and covering in dense random graphs
- 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 directed triangles
- Tuza's conjecture for graphs with maximum average degree less than 7
- Recent techniques and results on the Erdős-Pósa property
- Fractional \(K_{4}\)-covers
- Triangle packings and transversals of some \(K_{4}\)-free graphs
- Packings and coverings of v=3m+1 points with near-triangle factors
- Sufficient conditions for Tuza's conjecture on packing and covering triangles
- Total dual integrality of triangle covering
- Dense graphs with a large triangle cover have a large triangle packing
- The minimum number of triangles covering the edges of a graph
- Packing and covering tetrahedra
- A stability theorem on fractional covering of triangles by edges
- scientific article; zbMATH DE number 1275586 (Why is no real title available?)
- scientific article; zbMATH DE number 706830 (Why is no real title available?)
- scientific article; zbMATH DE number 1760745 (Why is no real title available?)
- Perfect Triangle Families
- Large triangle packings and Tuza's conjecture in sparse random 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
- Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
- Easily testable graph properties
- Tuza's conjecture is asymptotically tight for dense graphs
- On Tuza's conjecture for triangulations and graphs with small treewidth
- On Tuza's conjecture for triangulations and graphs with small treewidth
- Tuza's Conjecture for Threshold Graphs
- Tuza's conjecture for random graphs
- Packing and Covering a Given Directed Graph in a Directed Graph
- Generalized Tuza's conjecture for random hypergraphs
- Covering the edges of a graph with triangles
- Packing and covering triangles in bilaterally-complete tripartite graphs
- Monotonic decompositions of submodular set functions
- On Tuza's conjecture in dense graphs
- Approximate hypergraph vertex cover and generalized Tuza's conjecture
- New bounds on a generalization of Tuza's conjecture
- Covering triangles in edge-weighted graphs
- Packing and covering triangles in planar graphs
This page was built for publication: Packing and covering triangles in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296990)
