The Tuza–Vestergaard Theorem

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

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.

OriginalsprogEngelsk
TidsskriftSIAM Journal on Discrete Mathematics
Vol/bind37
Udgave nummer2
Sider (fra-til)1275-1310
Antal sider36
ISSN0895-4801
DOI
StatusUdgivet - 2023

Bibliografisk note

Funding Information:
*Received by the editors December 2, 2022; accepted for publication (in revised form) February 14, 2023; published electronically June 22, 2023. https://doi.org/10.1137/22M1475508 Funding: The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Wu\"rttemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B. \dagger Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa ([email protected], [email protected]). \ddagger Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark ([email protected]).

Funding Information:
The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Württemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B.

Publisher Copyright:
Copyright © by SIAM.

Fingeraftryk

Dyk ned i forskningsemnerne om 'The Tuza–Vestergaard Theorem'. Sammen danner de et unikt fingeraftryk.

Citationsformater