Hitting Maximum Independent Sets in Dense and Highly Connected Graphs

Abstract

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 \left\lfloor\frac{|V(G)|}{2α(G)+δ(G)-|V(G)|}\right\rfloor \] whenever the denominator is positive, with equality for balanced complete multipartite graphs. Consequently, every $3$-colorable graph of order $n$ with $κ(G)\geρn$ and $ρ>1/3$ has a hitting set of size at most $\lfloor(ρ-1/3)^{-1}\rfloor$; direct use of a $3$-coloring improves this to $6$ when $κ(G)>4n/9$ and to the sharp bound $3$ when $κ(G)>n/2$. For dense regular graphs with independence ratio greater than $1/4$, we obtain a logarithmic bound, while constructions with linear degree and linear independence number show that $h(G)=Ω(\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/3$ that explains the limitations of the degree-surplus and degree-ratio methods.

Disclosure

“all eligible G? An affirmative answer for all positive ρ ≤ 1/3, together with Corollary 5.1, would prove the Bollobás–Erdős–Tuza conjecture for all 3-colorable graphs. Acknowledgment. During the preparation of this work, the authors used ChatGPT 5.6 to improve the readability and language of the paper and to locate important references. The authors take full responsibility for all content of this work. References [1] J. Ai, H. Liu, Z. Xu and Q. Zhou, Piercing independent sets i”

PDF page 17

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-22T18:23:04.086118Z

Structural counts