2026/07/16 by Joshua Cooper, Isaiah Hollars
#math.CO
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 τ(G) the size of a smallest set of vertices T⊆ 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 τ(G)=o(n). Using a random construction, we show there exist c-hollow graphs with τ(G)=Ω(\fracn1/3log n ), 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.