THE TUZA-VESTERGAARD THEOREM

Michael A. Henning, Christian Löwenstein, Anders Yeo

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

The transversal number τ(H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then τ(H) ≤ 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture.

Original languageEnglish
Pages (from-to)1275-1310
Number of pages36
JournalSIAM Journal on Discrete Mathematics
Volume37
Issue number2
DOIs
Publication statusPublished - 2023

Keywords

  • hypergraph
  • transversal

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'THE TUZA-VESTERGAARD THEOREM'. Together they form a unique fingerprint.

Cite this