{"id":"arxiv/2608.18963","url":"https://arxiv.org/abs/2608.18963","tags":["math.CO"],"score":0,"title":"Hitting Maximum Independent Sets in Dense and Highly Connected Graphs","domain":"math.CO","source":"arxiv","authors":["Hanzhi Bai","Yufei Chang","Jin Yan"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}