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

For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $τ(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chvátal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $τ(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á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$.

No reviews yet.

No comments yet.