NP-completeness of recognizing well-covered graphs with two disjoint maximum independent sets
Statement
Let a graph be well-covered when all its maximal independent sets have the same cardinality; a maximum independent set is an independent set of cardinality . The recognition complexity claim. It is NP-complete to recognize well-covered graphs with two disjoint maximum independent sets.
This is a computational-complexity statement about recognizing graphs satisfying the specified structural property. The source states the claim but gives no further resolution or qualification.
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.