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

Joshua Cooper, Isaiah Hollars

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 sm…