Maximum stable sets in analogs of Kneser and complete graphs

DOI10.1016/J.EJC.2008.03.002zbMATH Open1207.05143OpenAlexW2069895083MaRDI QIDQ2519792FDOQ2519792

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

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

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)

Cites Work

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

Cited In (12)

• The number of all stable sets in some classes of graphs
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• Title not available (Why is that?)
• On the number of vertices belonging to all maximum stable sets of a graph
• Stable sets of maximal size in Kneser-type graphs
• Sink-Stable Sets of Digraphs
• Title not available (Why is that?)
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Maximum acyclic and fragmented sets in regular graphs
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size

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)