### 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 | The Electronic Journal of Combinatorics |

Volume | 23 |

Issue number | 3 |

ISSN | 1097-1440 |

Publication status | Published - 2016 |

### Fingerprint

### Keywords

- Hypergraph
- Transversal

### Cite this

*The Electronic Journal of Combinatorics*,

*23*(3).