A Generalization of the Erdös-Ko-Rado Theorem

2009/02/22 by Meysam Alishahi, Alishahi, Meysam, Hossein Hajiabolhassan +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.0902.3770

openalex publication_date 2009/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note, we investigate some properties of local Kneser graphs defined in [8]. In this regard, as a generalization of the Erd\rm os-Ko-Rado theorem, we characterize the maximum independent sets of local Kneser graphs. Next, we present an upper bound for their chromatic number.

Related

• Extremal G-free induced subgraphs of Kneser graphs
• On "stability" in the Erdős-Ko-Rado theorem
• Transference for the Erd\Hos-Ko-Rado theorem
• Colorful hypergraphs in Kneser hypergraphs
• On some topological and combinatorial lower bounds on chromatic number of Kneser type hyper graphs