The beta conjecture for maximal independent sets

Let GG be a graph on nn vertices, let i(G)i(G) be the size of a smallest maximal independent set, and let τ(G)\tau(G) be the transversal number of the family of maximal independent sets. Define

β(G)=τ(G)i(G)n.\beta(G)=\frac{\tau(G)i(G)}{n}.

Beta conjecture. For all graphs GG on nn vertices,

β(G)=o(n).\beta(G)=o(n).

This is presented as a reformulation of the Bollobás–Erdős–Tuza conjecture for cc-hollow graphs. The paper notes that it holds trivially when i(G)=o(n)i(G)=o(n), while the general assertion remains open.

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.