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

Abstract

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átal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $\tau (H)\le (n+\lfloor \frac{k}{2}\rfloor m)/(\lfloor \frac{3k}{2}\rfloor )$. When $k=3$, the connected hypergraphs that achieve equality in the Chvá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átal-McDiarmid Theorem for $k=2$ and for all $k\ge 4$.

12 pages