### Abstract

Let G be a tree and let ℋ be a collection of subgraphs of G, each having at most d connected components. Let v(ℋ) denote the maximum number of members of ℋ no two of which share a common vertex, and let τ(ℋ) denote the minimum cardinality of a set of vertices of G that intersects all members of ℋ. It is shown that τ(ℋ) ≤ 2d^{2}v(ℋ). A similar, more general result is proved replacing the assumption that G is a tree by the assumption that it has a bounded tree-width. These improve and extend results of various researchers.

Original language | English (US) |
---|---|

Pages (from-to) | 249-254 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 257 |

Issue number | 2-3 |

DOIs | |

State | Published - Nov 28 2002 |

Externally published | Yes |

Event | Kleitman and Combinatorics: A Celebration - Cambridge, MA, United States Duration: Aug 16 1990 → Aug 18 1990 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Covering a hypergraph of subgraphs'. Together they form a unique fingerprint.

## Cite this

Alon, N. (2002). Covering a hypergraph of subgraphs.

*Discrete Mathematics*,*257*(2-3), 249-254. https://doi.org/10.1016/S0012-365X(02)00427-2