Packing and covering triangles in graphs (Q1296990)

From MaRDI portal
Revision as of 03:51, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Packing and covering triangles in graphs
scientific article

    Statements

    Packing and covering triangles in graphs (English)
    0 references
    9 February 2000
    0 references
    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\).
    0 references
    0 references
    0 references
    packing
    0 references
    covering
    0 references
    transversal
    0 references
    independent family of triangles
    0 references
    0 references