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

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 05:08, 5 March 2024

scientific article
Language Label Description Also known as
English
Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
scientific article

    Statements

    Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs (English)
    0 references
    0 references
    12 February 1996
    0 references
    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.
    0 references
    maximal chain
    0 references
    maximal antichain
    0 references
    maximal cliques
    0 references
    maximal stable sets
    0 references
    partially ordered sets
    0 references
    ordered graphs
    0 references
    Chvátal's conjecture
    0 references
    Grillet's theorem
    0 references
    Berge's conjecture
    0 references

    Identifiers