Packing and covering triangles in graphs
type: Item
instance of: scholarly article
title: Packing and covering triangles in graphs
zbMATH Open document ID: 0930.05077
DOI: 10.1016/S0012-365X(98)00183-6
published in: Discrete Mathematics
publication date: 2000-02-09T00:00:00Z
review text: 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\).
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1320592
zbMATH Keywords: packing
zbMATH Keywords: covering
zbMATH Keywords: transversal
zbMATH Keywords: independent family of triangles
author: Penny Haxell
MaRDI profile type: Publication
cites work: Matchings and covers in hypergraphs
cites work: Packing and covering triangles in tripartite graphs
cites work: On a conjecture of Tuza about packing and covering of triangles
cites work: A conjecture on triangles of graphs
Recommended article: Packing and covering triangles in tripartite graphs
Recommended article: Packing triangles in a graph and its complement
Recommended article: Packing and covering directed triangles
Recommended article: Packing Triangles in Weighted Graphs
Recommended article: Packing triangles in bounded degree graphs.
Recommended article: Triangle packing and covering in dense random graphs
Recommended article: Packing and covering triangles in dense random graphs
Recommended article: Q3576699
Recommended article: Packing triangles in low degree graphs and indifference graphs
description: scientific article; zbMATH DE number 1320592