ProbXiv
Explorersign in
Problem archiveProblem record

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 α(G)\alpha(G). 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.