1993/07/01 by Michael D. Plummer · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs #Mathematics #Maximal independent set #Independent set #Independence (probability theory) #Combinatorics #Independence number #Set (abstract data type) #Property (philosophy) #Graph #Discrete mathematics #Chordal graph #1-planar graph #Computer science #Statistics
paper · doi:10.1080/16073606.1993.9631737
openalex publication_date 1993/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A graph G is well-covered (or w-c) if every maximal independent set of points in G is also maximum. Clearly, this is equivalent to the property that the greedy algorithm for constructing a maximal independent set always results in a maximum independent set. Although the problem of independence number is well-known to be NP-complete, it is trivially polynomial for well-covered graphs. The concept of well-coveredness was introduced by the author in [P1] and was first discussed therein with respect to its relationship to a number of other properties involving the independence number. Since then, a number of results about well-covered graphs have been obtained. It is our purpose in this paper to survey these results for the first time. As the reader will see, many of the results we will discuss are quite recent and have not as yet appeared in print.