Hitting all maximal independent sets in $c$-hollow graphs

Abstract

Fix a constant $c$ with $0<c<1$. We say a graph $G$ on $n$ vertices is $c$-hollow if every maximal independent set of $G$ has size at least $cn$. Denote by $\ddot{I}„(G)$ the size of a smallest set of vertices $T\subseteq V(G)$ such that every maximal independent set in $G$ intersects $T$, i.e., $T$ is a transversal for the family of maximal independent sets. In 1991, Bollobás, Erdős, and Tuza conjectured that if $G$ is $c$-hollow, then $\ddot{I}„(G)=o(n)$. Using a random construction, we show there exist $c$-hollow graphs with $\ddot{I}„(G)=\hat{I}\text{c◯}\left(\frac{n^{1/3}}{\log n}\right)$, establishing the first nontrivial lower bound constraining the conjecture and complementing a closely related lower bound due to Alon for maximum independent sets. We also show the conjecture holds in a strong form for the class of cographs and split graphs.

18 pages, 0 figures