On the number of minimal transversals in 3-uniform hypergraphs

Zbigniew Lonc, Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cn, where c ≈ 1.6702. The best known lower bound for this number, due to Tomescu, is adn, where d = 101 / 5 ≈ 1.5849 and a is a constant.

Original languageEnglish
Pages (from-to)3668-3687
Number of pages20
JournalDiscrete Mathematics
Issue number16
StatePublished - Aug 28 2008


  • Maximal independent set
  • Minimal transversal
  • Uniform hypergraph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the number of minimal transversals in 3-uniform hypergraphs'. Together they form a unique fingerprint.

Cite this