Bounding the vertex cover number of a hypergraph

Guo Li Ding, Paul Seymour, Peter Winkler

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

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 Kk. 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 languageEnglish (US)
Pages (from-to)23-34
Number of pages12
JournalCombinatorica
Volume14
Issue number1
DOIs
StatePublished - Mar 1994
Externally publishedYes

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