Strong conjecture on transversals of large maximal independent sets

Let 0<c<10<c<1 be a constant. For a graph GG, let MIS(G)\operatorname{MIS}(G) denote its family of maximal independent sets, and define the family of large maximal independent sets by

MISlarge(G)={IMIS(G):Icn}.\operatorname{MIS}_{\mathrm{large}}(G)=\{I\in\operatorname{MIS}(G): |I|\geq cn\}.

A transversal is a set of vertices meeting every member of this family. Strong conjecture. Every graph GG on nn vertices has a transversal of size o(n)o(n) for MISlarge(G)\operatorname{MIS}_{\mathrm{large}}(G). The source describes this as a stronger conjecture proposed tentatively, and provides no proof or counterexample; the supplied status evidence is inconsistent with the assertion and is therefore noted for review.

Sources & referencesView supporting material

Primary source

Joshua Cooper and Isaiah Hollars, “Hitting all maximal independent sets in c-hollow graphs”, arXiv:2607.15486 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.