Transversals in 4-uniform hypergraphs
type: Item
instance of: scholarly article
title: Transversals in 4-uniform hypergraphs
zbMATH Open document ID: 1351.05221
author: Michael A. Henning
author: A. Yeo
published in: The Electronic Journal of Combinatorics
publication date: 2016-12-06T00:00:00Z
full work available at URL: v23i3p50
review text: Summary: Let \(H\) be a \(4\)-uniform hypergraph on \(n\) vertices. The transversal number \(\tau(H)\) of \(H\) is the minimum number of vertices that intersect every edge. The result in [J. Comb. Theory, Ser. B 50, No. 1, 129--133 (1990; Zbl 0739.05068)] by \textit{F.-C. Lai} and \textit{G. H. Chang} implies that \(\tau(H) \leq 7n/18\) when \(H\) is \(3\)-regular. The main result in [Combinatorica 27, No. 4, 473--487 (2007; Zbl 1164.05052)] by \textit{S. Thomassé} and \textit{A. Yeo} implies an improved bound of \(\tau(H) \leq 8n/21\). We provide a further improvement and prove that \(\tau(H) \leq 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 \(\Delta(H) \leq 3\), then \(\tau(H) \leq 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 \(\tau(H) \leq \frac{3}{7}n\), which was the main result of the Thomassé-Yeo paper [loc. cit.].
Mathematics Subject Classification ID: 05D15
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6661286
zbMATH Keywords: transversal
zbMATH Keywords: hypergraph
MaRDI profile type: Publication
cites work: Transversals and domination in uniform hypergraphs
cites work: Small transversals in hypergraphs
cites work: Hypergraphs with large transversal number and with edge sizes at least four
cites work: Hypergraphs with large transversal number and with edge sizes at least 3
cites work: Strong Transversals in Hypergraphs and Double Total Domination in Graphs
cites work: Transversals and matchings in 3-uniform hypergraphs
cites work: Hypergraphs with large transversal number
cites work: Total Domination in Graphs
cites work: An upper bound for the transversal numbers of 4-uniform hypergraphs
cites work: The Tuza–Vestergaard Theorem
cites work: Total domination of graphs and small transversals of hypergraphs
cites work: Domination in partitioned graphs
Recommended article: Transversals in Uniform Linear Hypergraphs
Recommended article: An upper bound for the transversal numbers of 4-uniform hypergraphs
Recommended article: Transversal numbers of uniform hypergraphs
Recommended article: Transversals in linear uniform hypergraphs
Recommended article: Q3335828
Recommended article: Transversals and domination in uniform hypergraphs
Recommended article: Transversals in uniform hypergraphs with property \((p,2)\)
Recommended article: On \(P_4\)-transversals of perfect graphs
Recommended article: On \(P_4\)-transversals of chordal graphs
Recommended article: Total transversals and total domination in uniform hypergraphs
description: scientific article; zbMATH DE number 6661286