Well-Covered Graphs

The problem of determining which graphs have the property that every maximal independent set of vertices is also a maximum independent set was proposed by M.D. Plummer
in 1970 [28]. This was partly motivated by the observation that whereas determining the independence number of an arbitrary graph is NP-complete, for a well-covered graph one can
simply apply the greedy algorithm. Although a good deal of effort has been expended in an
attempt to obtain a complete characterization of such graphs, that result appears as elusive as ever. In this paper, intended to serve as an introduction to the problem, several of the main attacks will be highlighted with particular emphasis on the approach involving the girth of such graphs.