A conjecture on triangles of graphs
From MaRDI portal
The author conjectured in 1981: If a grah G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles of G. In the paper this conjecture is proved for various classes of graphs (planar graphs, graphs with n vertices and at least \((7/16)n^ 2\) edges, chordal graphs without a complete subgraph on 5 vertices). Related results for 3-uniform hypergraphs and digraphs as well as weaker and stronger versions of the conjecture for special classes of graphs are discussed. Open problems are presented.
Recommendations
Cites work
- Helly-type hypergraphs and Sperner families
- scientific article; zbMATH DE number 4065037 (Why is no real title available?)
- scientific article; zbMATH DE number 4196017 (Why is no real title available?)
- On rigid circuit graphs
- Triangle-free partial graphs and edge covering theorems
- Upper bound for transversals of tripartite hypergraphs
Cited in
(49)- Packing and covering triangles in graphs
- Edge-disjoint odd cycles in planar graphs.
- A semidefinite approach to the $K_i$-cover problem
- Graph edge coloring: a survey
- Strongly edge triangle regular graphs and a conjecture of Kotzig
- Triangles and neighbourhoods of independent sets in graphs
- Equivalences to the triangulation conjecture
- On a conjecture of Tuza about packing and covering of triangles
- Packing and covering triangles in \(K_{4}\)-free planar graphs
- Small edge sets meeting all triangles of a graph
- Packing triangles in \(K_4\)-free graphs
- 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
- On triangles in derangement graphs
- 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
- Graphs with \(\alpha _1\) and \(\tau _1\) both large
- Triangle packings and transversals of some \(K_{4}\)-free graphs
- Sufficient conditions for Tuza's conjecture on packing and covering triangles
- Total dual integrality of triangle covering
- Induced cycles in triangle graphs
- scientific article; zbMATH DE number 4066933 (Why is no real title available?)
- scientific article; zbMATH DE number 4085714 (Why is no real title available?)
- Packing and covering tetrahedra
- A stability theorem on fractional covering of triangles by edges
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Perfect Triangle Families
- Exposé Bourbaki 1163 : Manolescu's work on the Triangulation Conjecture
- A Turán-type generalization of Tuza's triangle edge cover problem
- Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
- On the Number of Triangles Contained in Certain Graphs
- On Tuza's conjecture for triangulations and graphs with small treewidth
- On Tuza's conjecture for triangulations and graphs with small treewidth
- Packing and Covering a Given Directed Graph in a Directed Graph
- Generalized Tuza's conjecture for random hypergraphs
- 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
- An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs
- Covering triangles in edge-weighted graphs
- On an extremal problem in graph theory.
- Dyck's map \(\{3,7\}_ 8\) is a counterexample to a clique covering conjecture
- Packing and covering triangles in planar graphs
This page was built for publication: A conjecture on triangles of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2276982)
