Triangle packings and transversals of some \(K_{4}\)-free graphs (Q2413632): Difference between revisions

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.