Triangle packings and transversals of some K₄-free graphs
Tuza's conjecture asserts that the minimum number of edges in a graph \(G\) whose deletion results in a triangle-free graph is at most 2 times the maximum number of edge-disjoint triangles in \(G\). The complete graphs \(K_4\) and \(K_5\) show that the constant 2 is best possible. A natural question is: What happens if we forbid \(K_4\)? \textit{P. Haxell} et al. [Eur. J. Comb. 33, No. 5, 799--806 (2012; Zbl 1239.05030)] al showed that even here the constant 2 essentially cannot be improved. They showed that for every \(\delta>0\), there exists a \(K_4\)-free graph \(G\) such that the minimum number of edges in \(G\) whose deletion results in a triangle-free graph is greater than (2-\(\delta\)) times the maximum number of edge disjoint triangles in \(G\). In this paper, the authors consider several classes of \(K_4\)-free graphs and show that the constant 2 can be improved for them. The classes investigated are of two kinds: graphs with edges in few triangles and graphs obtained by forbidding odd wheels.
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
- \(K_ i\)-covers. I: Complexity and polytopes
- \(K_{4}\)-free graphs with no odd holes
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A conjecture on triangles of graphs
- A stability theorem on fractional covering of triangles by edges
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Bounded clique cover of some sparse graphs
- Characterizations of derived graphs
- Complements of nearly perfect graphs
- Critical graphs with connected complements
- Gallai graphs and anti-Gallai graphs
- Generalized line graphs: Cartesian products and complexity of recognition
- Graph Theory and Probability
- scientific article; zbMATH DE number 4085709 (Why is no real title available?)
- scientific article; zbMATH DE number 3232667 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- Independence and matching number in graphs with maximum degree 4
- Independent sets and matchings in subcubic graphs
- Induced cycles in triangle graphs
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- Iterated k-line graphs
- Ki-covers. II.Ki-perfect graphs
- On a conjecture of Tuza about packing and covering of triangles
- On the hardness of recognizing triangular line graphs
- On the structure of (banner, odd hole)-free graphs
- On the tightness of the \(\frac {5}{14}\) independence ratio
- Packing and covering triangles in \(K_{4}\)-free planar graphs
- Packing and covering triangles in graphs
- Ryser's conjecture for tripartite 3-graphs
- Small edge sets meeting all triangles of a graph
- Some Ramsey-Type Numbers and the Independence Ratio
- The chromatic gap and its extremes
- The strong perfect graph theorem
- Transitiv orientierbare Graphen
- Tuza's conjecture for graphs with maximum average degree less than 7
- Two characterizations of interchange graphs of complete m-partite graphs
- Packing and covering triangles in \(K_{4}\)-free planar graphs
- Packing triangles in \(K_4\)-free graphs
- Triangle packing and covering in dense random graphs
- Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
- On the number of edge-disjoint triangles in \(K_4\)-free graphs
- On Tuza's conjecture in dense graphs
This page was built for publication: Triangle packings and transversals of some \(K_{4}\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413632)
