Transversals in 4-Uniform Hypergraphs

Original · EN

Let H be a 3-regular 4-uniform hypergraph on n vertices. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [J. Combin. Theory Ser. B 50 (1990), 129--133] proved that τ(H) ≤ 7n/18. Thomassé and Yeo [Combinatorica 27 (2007), 473--487] improved this bound and showed that τ(H) ≤ 8n/21. We provide a further improvement and prove that τ(H) ≤ 3n/8, which is best possible due to a hypergraph of order eight. More generally, we show that if H is a 4-uniform hypergraph on n vertices and m edges with maximum degree Δ(H) ≤ 3, then τ(H) ≤ n/4 + m/6, which proves a known conjecture. We show that an easy corollary of our main result is that the total domination number of a graph on n vertices with minimum degree at least 4 is at most 3n/7, which was the main result of the Thomassé-Yeo paper [Combinatorica 27 (2007), 473--487].