WELL-COVERED GRAPHS: A SURVEY
- 1 July 1993
- journal article
- research article
- Published by Taylor & Francis Ltd in Quaestiones Mathematicae
- Vol. 16 (3), 253-287
- https://doi.org/10.1080/16073606.1993.9631737
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- A Characterization of Well Covered Graphs of Girth 5 or GreaterJournal of Combinatorial Theory, Series B, 1993
- Complexity results for well‐covered graphsNetworks, 1992
- Cyclic coloration of 3‐polytopesJournal of Graph Theory, 1987
- Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoileDiscrete Mathematics, 1980
- Independence numbers of graphs-an extension of the Koenig-Egervary theoremDiscrete Mathematics, 1979
- On some subclasses of well‐covered graphsJournal of Graph Theory, 1979
- Matchings in polytopal graphsNetworks, 1974
- Some covering concepts in graphsJournal of Combinatorial Theory, 1970
- A Theorem on k-Saturated GraphsCanadian Journal of Mathematics, 1965
- The Factorization of Linear GraphsJournal of the London Mathematical Society, 1947