Covering a hypergraph of subgraphs
type: Item
instance of: scholarly article
title: Covering a hypergraph of subgraphs
zbMATH Open document ID: 1013.05060
DOI: 10.1016/S0012-365X(02)00427-2
author: Noga Alon
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: Let \(H\) be a collection of subgraphs of a tree \(G\), each of which has at most \(d\) connected components. Let \(\nu(H)\) be the maximum number of members of \(H\), no two of which share a common vertex, and let \(\tau(H)\) be the minimum cardinality of a set of vertices of \(G\) that intersects all members of \(H\). The paper shows that \(\tau(H)\leq 2d^2\nu(H)\). This result is then extended to the situation where \(G\) is not a tree but it has a bounded tree-width.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1838990
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1838990