Linear hypergraphs with large transversal number and maximum degree two

For k ≥ 2, let H be a k-uniform hypergraph on n vertices and m edges. The transversal number τ (H) of H is the minimum number of vertices that intersect every edge. Chvátal and McDiarmid [V. Chvátal, C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19-26] proved that τ(H)≤(n+⌊⌋m)/(⌊3⌋). In particular, for k ∈ {2, 3} we have that (k + 1) τ (H) ≤ n + m. A linear hypergraph is one in which every two distinct edges of H intersect in at most one vertex. In this paper, we consider the following question posed by Henning and Yeo: Is it true that if H is linear, then (k + 1) τ (H) ≤ n + m holds for all k ≥ 2? If k ≥ 4 and we relax the linearity constraint, then this is not always true. We show that if δ (H) ≤ 2, then (k + 1) τ (H) ≤ n + m does hold for all k ≥ 2 and we characterize the hypergraphs achieving equality in this bound.