×

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].

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
PDFBibTeX XMLCite