The maximal-independent-set conjecture for graphs with perfect matchings
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.