pith. sign in

arxiv: 0903.4203 · v2 · submitted 2009-03-24 · 🧮 math.CO

Erd\"os-Ko-Rado theorems for chordal and bipartite graphs

classification 🧮 math.CO
keywords graphsos-ko-radochordalindependentprovesizecompletefamily
0
0 comments X
read the original 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 $r$ 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 $r\leq mu(G)/2$, 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.