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

DOI10.1016/J.DISC.2009.07.020MaRDI QIDQ1045161zbMATH OpenOpenAlexFDO

Authors Meysam Alishahi, Hossein Hajiabolhassan, Ali Taherkhani

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A note on the star chromatic number
• Coloring graphs with locally few colors
• Homomorphisms of 3-chromatic graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number and Sperner capacity
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number of quadrangulations of surfaces
• Local chromatic number, Ky Fan's theorem, and circular colorings
• 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
• scientific article; zbMATH DE number 701002 (Why is no real title available?)
• A short proof of an Erdős-Ko-Rado theorem for compositions
• Erdős-Ko-Rado theorems on the weak Bruhat lattice
• On the maximum size of Erdős-Ko-Rado sets in \(H(2d+1, q^2)\)
• scientific article; zbMATH DE number 4179418 (Why is no real title available?)
• 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
• The exact bound in the Erdős-Ko-Rado theorem
• An Erdős--Ko--Rado theorem for partial permutations
• An Erdös-Ko-Rado theorem for direct products
• A continuous analogue of Erdős' \(k\)-Sperner theorem
• Maximum stable sets in analogs of Kneser and complete graphs
• An Erdős-Ko-Rado theorem for signed sets
• Some Erdős-Ko-Rado theorems for injections
• The Erdős-Ko-Rado theorem for integer sequences
• Sharp threshold for the Erdős–Ko–Rado theorem
• Erdös-Ko-Rado theorem for ladder graphs
• scientific article; zbMATH DE number 1420985 (Why is no real title available?)
• scientific article; zbMATH DE number 5130735 (Why is no real title available?)
• A Short Proof for an Extension of the Erdős–Ko–Rado Theorem
• A general Darling-Erdős theorem in Euclidean space
• AN ERDŐS-KO-RADO THEOREM FOR MINIMAL COVERS

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)