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 $τ(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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.15486
curl -X POST /api/v1/records/arxiv/2607.15486/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.15486/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'