Erdős-Ko-Rado theorems for chordal graphs and trees
From MaRDI portal
Publication:2431248
DOI10.1016/J.JCTA.2010.11.017zbMATH Open1238.05219arXiv0903.4203OpenAlexW2008327005MaRDI QIDQ2431248FDOQ2431248
Authors: Vikram Kamat, Glenn H. Hurlbert 
Publication date: 11 April 2011
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: One of the more recent generalizations of the Erd"os-Ko-Rado theorem, formulated by Holroyd, Spencer and Talbot, defines the Erd"os-Ko-Rado property for graphs in the following manner: for a graph G and a positive integer r, G is said to be r-EKR if no intersecting subfamily of the family of all independent vertex sets of size r is larger than the largest star, where a star centered at a vertex v is the family of all independent sets of size containing v. In this paper, we prove that if G is a disjoint union of chordal graphs, including at least one singleton, then G is r-EKR if , where mu(G) is the minimum size of a maximal independent set. We will also prove Erd"os-Ko-Rado results for chains of complete graphs, which are a class of chordal graphs obtained by blowing up edges of a path into complete graphs. We also consider similar problems for ladder graphs and trees, and prove preliminary results for these graphs.
Full work available at URL: https://arxiv.org/abs/0903.4203
Recommendations
Cites Work
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- On rigid circuit graphs
- An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
- Erdös–Ko–Rado Theorem—22 Years Later
- Title not available (Why is that?)
- The Erdős-Ko-Rado properties of various graphs containing singletons
- Compression and Erdős-Ko-Rado graphs
- Graphs with the Erdős-Ko-Rado property
- Title not available (Why is that?)
- An ordered version of the Erdős-Ko-Rado theorem
- INTERSECTING FAMILIES OF SEPARATED SETS
- More on the Erdős-Ko-Rado theorem for integer sequences
Cited In (31)
- An Erdős-Ko-Rado theorem for unions of length 2 paths
- The Erdős-Ko-Rado properties of various graphs containing singletons
- Compression and Erdős-Ko-Rado graphs
- Graphs with the Erdős-Ko-Rado property
- Erdős-Ko-Rado theorems for simplicial complexes
- Restricted intersecting families on simplicial complex
- Strong Erdős-Hajnal properties in chordal graphs
- Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- The number of \(s\)-separated \(k\)-sets in various circles
- The Erdős-Ko-Rado theorem for twisted Grassmann graphs
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- On stars in caterpillars and lobsters
- On the Holroyd-Talbot conjecture for sparse graphs
- A Deza-Frankl type theorem for set partitions
- A generalization of the Erdős-Ko-Rado theorem
- On the star of the family of independent sets in a graph
- A non-trivial intersection theorem for permutations with fixed number of cycles
- An EKR-theorem for finite buildings of type \(D_{\ell }\)
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- Very well-covered graphs with the Erdős-Ko-Rado property
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- On intersecting families of independent sets in trees
- Erdös-Ko-Rado theorems for a family of trees
- Cross-intersecting subfamilies of levels of hereditary families
- Erdös-Ko-Rado theorem for ladder graphs
- Title not available (Why is that?)
- Strongly intersecting integer partitions
- Stars on trees
- Non-trivial intersecting uniform sub-families of hereditary families
This page was built for publication: Erdős-Ko-Rado theorems for chordal graphs and trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431248)
