THE TUZA-VESTERGAARD THEOREM

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

doi:10.1137/22M1475508

THE TUZA-VESTERGAARD THEOREM

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

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

2 Citations (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 language	English
Pages (from-to)	1275-1310
Number of pages	36
Journal	SIAM Journal on Discrete Mathematics
Volume	37
Issue number	2
DOIs	https://doi.org/10.1137/22M1475508
Publication status	Published - 2023

Keywords

hypergraph
transversal

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1137/22M1475508

Cite this

@article{74a64b4883b1482d8af3c7736787139f,

title = "THE TUZA-VESTERGAARD THEOREM",

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.",

keywords = "hypergraph, transversal",

author = "Henning, {Michael A.} and Christian L{\"o}wenstein and Anders Yeo",

note = "Publisher Copyright: Copyright {\textcopyright} by SIAM.",

year = "2023",

doi = "10.1137/22M1475508",

language = "English",

volume = "37",

pages = "1275--1310",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - THE TUZA-VESTERGAARD THEOREM

AU - Henning, Michael A.

AU - Löwenstein, Christian

AU - Yeo, Anders

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - hypergraph

KW - transversal

UR - http://www.scopus.com/inward/record.url?scp=85166005667&partnerID=8YFLogxK

U2 - 10.1137/22M1475508

DO - 10.1137/22M1475508

M3 - Article

AN - SCOPUS:85166005667

SN - 0895-4801

VL - 37

SP - 1275

EP - 1310

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

THE TUZA-VESTERGAARD THEOREM

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this