Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs

DOI10.1016/0012-365X(94)00019-FMaRDI QIDQ1897443zbMATH OpenWikidataFDO

Authors Wenan Zang

Publication date 12 February 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00019-F

zbMATH Keywords

Berge's conjectureChvátal's conjectureGrillet's theoremmaximal antichainmaximal chainmaximal cliquesmaximal stable setsordered graphspartially ordered sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)

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.

Recommendations

• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs
• Using stable sets to bound the chromatic number
• The strong perfect graph theorem
• A note on hitting maximum and maximal cliques with a stable set

Cites work

• \(P_ 4\)-comparability graphs
• Maximal chains and antichains

Cited in

(22)

• Graphs vertex-partitionable into strong cliques
• Stable sets of maximal size in Kneser-type graphs
• On the number of vertices belonging to all maximum stable sets of a graph
• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Unconditional reflexive polytopes
• Detecting strong cliques
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• Strong cliques and equistability of EPT graphs
• On equistable, split, CIS, and related classes of graphs
• scientific article; zbMATH DE number 5781390 (Why is no real title available?)
• On CIS circulants
• Vertex-transitive CIS graphs
• Strong cliques in diamond-free graphs
• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Strong cliques in vertex‐transitive graphs
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Upper Clique Transversals in Graphs
• More on discrete convexity
• Conformal hypergraphs: duality and implications for the upper clique transversal problem
• Not complementary connected and not CIS d-graphs form weakly monotone families
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs

This page was built for publication: Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1897443)