## Abstract

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

Original language | English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 23 |

Issue number | 3 |

DOIs | |

Publication status | Published - 30 Sept 2016 |

## Keywords

- Hypergraph
- Transversal

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics