### Abstract

For a hypergraph H, we denote by (i) τ(H) the minimum k such that some set of k vertices meets all the edges, (ii) ν(H) the maximum k such that some k edges are pairwise disjoint, and (iii) λ(H) the maximum k≥2 such that the incidence matrix of H has as a submatrix the transpose of the incidence matrix of the complete graph K_{k}. We show that τ(H) is bounded above by a function of ν(H) and λ(H), and indeed that if λ(H) is bounded by a constant then τ(H) is at most a polynomial function of ν(H).

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

Pages (from-to) | 23-34 |

Number of pages | 12 |

Journal | Combinatorica |

Volume | 14 |

Issue number | 1 |

DOIs | |

State | Published - Mar 1 1994 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

### Keywords

- AMS subject classification codes (1991): 05C65, 05C35

## Fingerprint Dive into the research topics of 'Bounding the vertex cover number of a hypergraph'. Together they form a unique fingerprint.

## Cite this

Ding, G. L., Seymour, P., & Winkler, P. (1994). Bounding the vertex cover number of a hypergraph.

*Combinatorica*,*14*(1), 23-34. https://doi.org/10.1007/BF01305948