Erdős-Ko-Rado theorems for chordal graphs and trees
From MaRDI portal
Publication:2431248
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3461973 (Why is no real title available?)
- scientific article; zbMATH DE number 3472087 (Why is no real title available?)
- An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
- An ordered version of the Erdős-Ko-Rado theorem
- Compression and Erdős-Ko-Rado graphs
- Erdös–Ko–Rado Theorem—22 Years Later
- Graphs with the Erdős-Ko-Rado property
- INTERSECTING FAMILIES OF SEPARATED SETS
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- More on the Erdős-Ko-Rado theorem for integer sequences
- On rigid circuit graphs
- The Erdős-Ko-Rado properties of various graphs containing singletons
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
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- Strong Erdős-Hajnal properties in chordal graphs
- Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
- New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- The number of \(s\)-separated \(k\)-sets in various circles
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- The Erdős-Ko-Rado theorem for twisted Grassmann graphs
- On stars in caterpillars and lobsters
- On the Holroyd-Talbot conjecture for sparse graphs
- A generalization of the Erdős-Ko-Rado theorem
- A Deza-Frankl type theorem for set partitions
- 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
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Very well-covered graphs with the Erdős-Ko-Rado property
- 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
- Strongly intersecting integer partitions
- scientific article; zbMATH DE number 5130735 (Why is no real title available?)
- 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)
