Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs (Q1897443): Difference between revisions

This paper presents four main theorems and generalizes Grillet's work on maximal stable sets in the spirit of Berge's proposal that Grillet's theorem can be stated in terms of graphs rather than partially ordered sets. Chvátal had proposed a conjecture as a variation on Berge's problem concerning beautifully ordered graphs. Two of the theorems proved in the paper are weaker than Chvátal's conjecture but stronger than Grillet's theorem. The remaining two theorems generalize Grillet's theorem in the spirit of Berge's conjecture.