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