A generalization of the Erdős-Ko-Rado theorem

DOI10.1016/J.DISC.2009.07.020zbMATH Open1181.05033arXiv0902.3770OpenAlexW2001098489MaRDI QIDQ1045161FDOQ1045161

Authors: Meysam Alishahi, Hossein Hajiabolhassan, Ali Taherkhani 

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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

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

Recommendations

• Graphs with the Erdős-Ko-Rado property
• On ``stability in the Erdős-Ko-Rado theorem
• Erdős-Ko-Rado theorems for chordal graphs and trees
• On the stability of the Erdős-Ko-Rado theorem
• On the stability of some Erdős-Ko-Rado type results

zbMATH Keywords

graph homomorphismKneser graphlocal chromatic numbermaximum independent setsErdős-Ko-Rado theorem

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)

Cites Work

• Homomorphisms of 3-chromatic graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• Coloring graphs with locally few colors
• Local chromatic number and Sperner capacity
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number, Ky Fan's theorem, and circular colorings
• A note on the star chromatic number
• Local chromatic number of quadrangulations of surfaces
• Locally restricted colorings

Cited In (27)

• Erdős-Ko-Rado theorems of labeled sets
• A generalization of a conjecture due to Erdös, Jacobson and Lehel
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• Dynamic coloring of graphs having no \(K_5\) minor
• Title not available (Why is that?)
• Erdős-Ko-Rado theorems on the weak Bruhat lattice
• A short proof of an Erdős-Ko-Rado theorem for compositions
• On the maximum size of Erdős-Ko-Rado sets in \(H(2d+1, q^2)\)
• Title not available (Why is that?)
• Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem
• On a generalized Erdős–Rademacher problem
• Erdös-Ko-Rado from intersecting shadows
• An Erdös-Ko-Rado theorem for direct products
• The exact bound in the Erdős-Ko-Rado theorem
• An Erdős--Ko--Rado theorem for partial permutations
• A continuous analogue of Erdős' \(k\)-Sperner theorem
• Maximum stable sets in analogs of Kneser and complete graphs
• The Erdős-Ko-Rado theorem for integer sequences
• An Erdős-Ko-Rado theorem for signed sets
• Some Erdős-Ko-Rado theorems for injections
• Sharp threshold for the Erdős–Ko–Rado theorem
• Title not available (Why is that?)
• Erdös-Ko-Rado theorem for ladder graphs
• Title not available (Why is that?)
• A Short Proof for an Extension of the Erdős–Ko–Rado Theorem
• AN ERDŐS-KO-RADO THEOREM FOR MINIMAL COVERS
• A general Darling-Erdős theorem in Euclidean space

This page was built for publication: A generalization of the Erdős-Ko-Rado theorem

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