Chvátal, Václav; Slater, Peter J. A note on well-covered graphs. (English) Zbl 0801.68119 Gimbel, John (ed.) et al., Quo vadis, graph theory? A source book for challenges and directions. Amsterdam: North-Holland. Ann. Discrete Math. 55, 179-181 (1993). Summary: It is shown that determining if a graph \(G\) is not well-covered is an NP- complete problem.For the entire collection see [Zbl 0773.00007]. Cited in 1 ReviewCited in 46 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C35 Extremal problems in graph theory Keywords:3-satisfiability; well-covered graphs; NP-complete PDFBibTeX XMLCite \textit{V. Chvátal} and \textit{P. J. Slater}, Ann. Discrete Math. 55, 179--181 (1993; Zbl 0801.68119)