The maximal-independent-set conjecture for graphs with perfect matchings
The maximal-independent-set conjecture for graphs with perfect matchings
Let be a graph on vertices containing a perfect matching. A maximal independent set is an independent vertex set that is not properly contained in any larger independent set. The perfect-matching maximal-independent-set conjecture. contains at most
maximal independent sets. This is posed as a conjecture about extremal enumeration in graphs with perfect matchings; the source gives no resolution, so the asserted bound remains open.
Sources & referencesView supporting material
Primary source
Nathanaël Hassler and Andrew Treglown, “Notes on sum-free sets in abelian groups”, arXiv:2506.17401 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.