Packing and covering triangles in graphs (Q1296990)
From MaRDI portal
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
packing
0 references
covering
0 references
transversal
0 references
independent family of triangles
0 references