Hitting Maximum Independent Sets in Dense and Highly Connected Graphs

For a graph $G$, let $h(G)$ be the minimum cardinality of a vertex set meeting every maximum independent set of $G$. We establish two complementary reduction principles for the Bollobás–Erdős–Tuza conjecture: the conjecture for arbitrary graphs is equivalent to its restriction to regular graphs of any fixed positive linear degree, and, within every hereditary graph class, a uniform sublinear bound is equivalent to a sublinear bound on graphs of every fixed positive linear vertex connectivity. We prove the sharp general estimate $$h(G)\le \lfloor \frac{\mathrm{\mid }V(G)\mathrm{\mid }}{2\alpha (G)+\delta (G)-\mathrm{\mid }V(G)\mathrm{\mid }}\rfloor$$ whenever the denominator is positive, with equality for balanced complete multipartite graphs. Consequently, every $3$-colorable graph of order $n$ with $\kappa (G)\ge \rho n$ and $\rho >1\mathrm{/}3$ has a hitting set of size at most $\lfloor (\rho -1\mathrm{/}3{)}^{-1}\rfloor$; direct use of a $3$-coloring improves this to $6$ when $\kappa (G)>4n\mathrm{/}9$ and to the sharp bound $3$ when $\kappa (G)>n\mathrm{/}2$. For dense regular graphs with independence ratio greater than $1\mathrm{/}4$, we obtain a logarithmic bound, while constructions with linear degree and linear independence number show that $h(G)=\mathrm{\Omega }(\sqrt{n})$ can still occur. We also prove a logarithmic bound for near-regular $3$-colorable graphs and exhibit a critical family at connectivity $n\mathrm{/}3$ that explains the limitations of the degree-surplus and degree-ratio methods.