Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
type: Item
instance of: scholarly article
title: Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
zbMATH Open document ID: 0831.05036
DOI: 10.1016/0012-365X(94)00019-F
author: Wenan Zang
published in: Discrete Mathematics
publication date: 1996-02-12T00:00:00Z
review text: 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.
reviewed by: Bai Kishan Dass
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 790558
zbMATH Keywords: maximal chain
zbMATH Keywords: maximal antichain
zbMATH Keywords: maximal cliques
zbMATH Keywords: maximal stable sets
zbMATH Keywords: partially ordered sets
zbMATH Keywords: ordered graphs
zbMATH Keywords: Chvátal's conjecture
zbMATH Keywords: Grillet's theorem
zbMATH Keywords: Berge's conjecture
MaRDI profile type: Publication
cites work: Maximal chains and antichains
cites work: \(P_ 4\)-comparability graphs
Wikidata QID: Q127109373
description: scientific article; zbMATH DE number 790558