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)

zbMATH Keywords

partially ordered setsmaximal cliquesmaximal chainmaximal stable setsmaximal antichainBerge's conjectureordered graphsGrillet's theoremChvátal's conjecture

Mathematics Subject Classification ID

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

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

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

Cited in

(20)

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

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)