Hitting Maximum Independent Sets in Dense and Highly Connected Graphs

@misc{bai2026hitting,
  title = {{Hitting Maximum Independent Sets in Dense and Highly Connected Graphs}},
  author = {Hanzhi Bai and Yufei Chang and Jin Yan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.18963},
  eprint = {2608.18963},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.18963},
  note = {CC0},
}

TY  - UNPB
TI  - Hitting Maximum Independent Sets in Dense and Highly Connected Graphs
AU  - Hanzhi Bai
AU  - Yufei Chang
AU  - Jin Yan
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2608.18963
UR  - https://arxiv.org/abs/2608.18963
AB  - 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)≤ ⌊|V(G)|/(2α(G)+δ(G)−|V(G)|)⌋ whenever the denominator is positive, with equality for balanced complete multipartite graphs. Consequently, every $3$-colorable graph of order n with κ(G)≥ρn and ρ>1/3 has a hitting set of size at most ⌊(ρ−1/3)^−1⌋; 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)=Ω(√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.
ER  -