{"id":"arxiv/2607.15486","url":"https://arxiv.org/abs/2607.15486","tags":["math.CO"],"score":0,"title":"Hitting all maximal independent sets in $c$-hollow graphs","domain":"math.CO","source":"arxiv","authors":["Joshua Cooper","Isaiah Hollars"],"reviews":0,"subject":"math.CO","summary":"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\\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 $τ(G)=o(n)$. Using a random construction, we show there exist $c$-hollow graphs with $τ(G)=Ω\\left(\\frac{n^{1/3}}{\\log n }\\right)$, establishing the first nontrivial…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}