Let H be a 4-uniform hypergraph on n vertices. The transversal number τ (H) of H is the minimum number of vertices that intersect every edge. The result in [J. Combin. Theory Ser. B 50 (1990), 129-133] by Lai and Chang implies that τ (H) ≤ 7n/18 when H is 3-regular. The main result in [Combinatorica 27 (2007), 473-487] by Thomassé and Yeo implies an improved bound of τ (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 if H is a 4-uniform hypergraph with n vertices and n edges, then τ (H) ≤ 3/ 7 n, which was the main result of the Thomassé-Yeo paper [Combinatorica 27 (2007), 473-487].
|Journal||The Electronic Journal of Combinatorics|
|Publication status||Published - 2016|