{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.18963",
  "author_total": 3,
  "authors": [
    {
      "name": "Hanzhi Bai"
    },
    {
      "name": "Yufei Chang"
    },
    {
      "name": "Jin Yan"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/5eeqwdjjgwr7w.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.18963",
  "fulltext_url": null,
  "id": "5eeqwdjjgwr7w",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.18963",
  "language": null,
  "licence": "CC0-1.0",
  "licence_label": "CC0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/publicdomain/zero/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "2607|Limits and Structures in Graph Theory"
    ]
  ],
  "openalex": "W7203892624",
  "pdf_url": "https://arxiv.org/pdf/2608.18963",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-08",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/5eeqwdjjgwr7w.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:20:01Z",
      "native_id": "2608.18963",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.18963"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Hitting Maximum Independent Sets in Dense and Highly Connected Graphs",
  "title_text": "Hitting Maximum Independent Sets in Dense and Highly Connected Graphs",
  "type": "preprint",
  "updated_at": "2026-10-30T12:20:01Z",
  "url": "https://research.draconitic.com/paper/5eeqwdjjgwr7w",
  "venue": "arXiv",
  "versions": []
}