A characterization of well-covered graphs in terms of forbidden costable subgraphs
A graph is called well-covered if all maximal independent sets have the same number of vertices. A subgraph of a graph \(G\) is called costable by the author if it is an induced subgraph that results from \(G\) by the deletion of an independent set in \(G\) together with its neighbourhood. So the costable subgraphs of a graph are a subset of its induced subgraphs. The author finds several connections between the class of well-covered graphs and the costable subgraph relation: The class of well-covered graphs is closed under taking costable subgraphs, and it can be described by the `forbidden subgraphs', those graphs never occuring as costable subgraph of a well-covered graph (so it is the maximal class with that set of forbidden subgraphs). He gives a description of a set of forbidden subgraphs generating the well-covered graphs: the joins of several well-covered graphs with distinct independence number. Some consequences are also discussed.
scientific article; zbMATH DE number 1517719