Maximum stable sets in analogs of Kneser and complete graphs

DOI10.1016/J.EJC.2008.03.002MaRDI QIDQ2519792zbMATH OpenOpenAlexFDO

Authors Gabor Kun, Benoît Larose

Publication date 27 January 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2008.03.002

zbMATH Keywords

maximum stable setsoptimal vertex coloringpowers of complete graphsvertex transitive subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Extremal set theory (05D05)

Recommendations

• Stable sets of maximal size in Kneser-type graphs
• On the stability of some Erdős-Ko-Rado type results
• On ``stability in the Erdős-Ko-Rado theorem
• A generalization of the Erdős-Ko-Rado theorem
• Bounded Stable Sets: Polytopes and Colorings

Cites work

• An Erdős--Ko--Rado theorem for partial permutations
• Applications of product colouring
• Graph products, Fourier analysis and spectral techniques
• Homomorphisms of 3-chromatic graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting families in the alternating group and direct product of symmetric groups
• Intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• Stable sets of maximal size in Kneser-type graphs

Cited in

(12)

• scientific article; zbMATH DE number 220408 (Why is no real title available?)
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Sink-Stable Sets of Digraphs
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Stable sets of maximal size in Kneser-type 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?)
• Maximum acyclic and fragmented sets in regular graphs
• On the number of vertices belonging to all maximum stable sets of a graph
• Maximum-weight stable sets and safe lower bounds for graph coloring
• The number of all stable sets in some classes of graphs

This page was built for publication: Maximum stable sets in analogs of Kneser and complete graphs

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