Packing and covering triangles in graphs (Q1296990)

From MaRDI portal
Revision as of 21:30, 28 May 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
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