Covering a hypergraph of subgraphs (Q1850010): Difference between revisions

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.