A characterization of claw-free CIS graphs and new results on the order of CIS graphs

DOI10.1016/J.ENTCS.2019.08.003MaRDI QIDQ2132328zbMATH OpenOpenAlexWikidataFDO

Authors L. Alcón, M. Gutierrez, Martin Milanič

Publication date 27 April 2022

Full work available at URL https://arxiv.org/abs/1812.05314

zbMATH Keywords

claw-free graphmaximal independent setCIS graphmaximal cliquemaximal stable setrandomly internally matchable graph

Mathematics Subject Classification ID

Graph theory (05Cxx) Mathematical programming (90Cxx)

Recommendations

• On graphs whose maximal cliques and stable sets intersect
• A characterization of almost CIS graphs
• On split and almost CIS-graphs
• On CIS circulants
• Vertex-transitive CIS graphs

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A characterization of perfect graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A structure theorem for maximum internal matchings in graphs
• Bipartite bihypergraphs: a survey and new results
• Complement reducible graphs
• Deciding the deterministic property for soliton graphs
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• Equistarable bipartite graphs
• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Graphs vertex-partitionable into strong cliques
• Line Graphs of Helly Hypergraphs
• Not complementary connected and not CIS \(d\)-graphs form weakly monotone families
• On CIS circulants
• On equistable, split, CIS, and related classes of graphs
• On graphs whose maximal cliques and stable sets intersect
• 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
• Ramsey-type theorems
• Randomly matchable graphs
• The Erdős-Hajnal conjecture. A survey
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Tutte type theorems for graphs having a perfect internal matching
• Vertex-transitive CIS graphs

Cited in

(3)

• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Strong cliques in diamond-free graphs
• Claw-free cubic graphs with clique-transversal number half of their order

This page was built for publication: A characterization of claw-free CIS graphs and new results on the order of CIS graphs

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