Packing and covering triangles in tripartite graphs
type: Item
instance of: scholarly article
title: Packing and covering triangles in tripartite graphs
zbMATH Open document ID: 0895.05048
published in: Graphs and Combinatorics
publication date: 1998-09-06T00:00:00Z
review text: This paper concerns an unresolved conjecture of \textit{Zs. Tuza} [Proc. Colloq. Math. Soc. János Bolyai 37 (1984), p. 808]. A set of triangles in a graph \(G\) is called independent if the triangles are pairwise edge-disjoint. Denote by \(\nu (G)\) the maximum cardinality of an independent set of triangles in \(G\). A set \(C\) of edges of \(G\) is called a transversal for \(G\) if every triangle of \(G\) contains at least one edge in \(C\). Denote by \(\tau (G)\) the minimum cardinality of a transversal for \(G\). Tuza conjectured that \(\tau (G) \leq 2 \nu (G)\) for every graph \(G\). The authors prove that for every tripartite graph \(G\) one has \(\tau(G) \leq (2-\varepsilon) \nu (G)\) where \(\varepsilon > 0.044\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05D15
zbMATH DE Number: 1146342
zbMATH Keywords: packing
zbMATH Keywords: covering
zbMATH Keywords: triangles
zbMATH Keywords: tripartite graphs
zbMATH Keywords: Tuza's conjecture
author: Penny Haxell
author: Yoshiharu Kohayakawa
reviewed by: Andrew Vince
MaRDI profile type: Publication
full work available at URL: s003730050010
OpenAlex ID: W2049672706
DOI: 10.1007/S003730050010
description: scientific article; zbMATH DE number 1146342