Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs

DOI10.1016/j.jctb.2004.03.002zbMath1048.05048OpenAlexW1969734816MaRDI QIDQ598473

Xiaotie Deng, Wenan Zang, Guo Jun Li

Publication date: 6 August 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2004.03.002

zbMATH Keywords

maximal chainpartially ordered setmaximal antichain

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items (8)

A characterization of claw-free CIS graphs and new results on the order of CIS graphs ⋮ On CIS circulants ⋮ On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems ⋮ Vertex-transitive CIS graphs ⋮ 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 ⋮ Strong cliques in diamond-free graphs

Cites Work

• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Transitiv orientierbare Graphen
• Maximal chains and antichains
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item

This page was built for publication: Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs