A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem

Michael A. Henning, Christian Löwenstein

Published 2014-01-20Version 1

For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $\tau(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chv\'{a}tal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $\tau(H)\le ( n + \left\lfloor \frac k2 \right\rfloor m )/ ( \left\lfloor \frac{3k}2 \right\rfloor )$. When $k = 3$, the connected hypergraphs that achieve equality in the Chv\'{a}tal-McDiarmid Theorem were characterized by Henning and Yeo [J. Graph Theory 59 (2008), 326--348]. In this paper, we characterize the connected hypergraphs that achieve equality in the Chv\'{a}tal-McDiarmid Theorem for $k = 2$ and for all $k \ge 4$.