Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs

DOI10.1007/S10255-006-6185-0zbMATH Open1213.05197OpenAlexW1982773847WikidataQ123197345 ScholiaQ123197345MaRDI QIDQ993683FDOQ993683

Authors Jing Sun, Zhiquan Hu 

Publication date 20 September 2010

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10255-006-6185-0

zbMATH Keywords

planar graphmaximal cliquemaximal stable set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Maximum induced forests of planar graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• A note on hitting maximum and maximal cliques with a stable set
• Covering all cliques of a graph

• scientific article; zbMATH DE number 3172312 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Maximal chains and antichains
• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Transitiv orientierbare Graphen

Cited In (7)

• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• A note on hitting maximum and maximal cliques with a stable set
• Matrix formulation of EISs of graphs and its application to WSN covering problems
• Vertex-transitive CIS graphs
• Towards Erdős-Hajnal for graphs with no 5-hole

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

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