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

From MaRDI portal
Revision as of 14:23, 16 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Triangle packings and transversals of some \(K_{4}\)-free graphs
scientific article

    Statements

    Triangle packings and transversals of some \(K_{4}\)-free graphs (English)
    0 references
    0 references
    14 September 2018
    0 references
    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.
    0 references
    triangle packing and transversal
    0 references
    \(\chi \)-bounded
    0 references
    triangle graphs
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers