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

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 $\tau(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 $\tau(G)=o(n)$.

Using a random construction, we show there exist $c$-hollow graphs with $\tau(G)=\Omega\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.