Erdős–Ko–Rado property for independent sets in disjoint unions of claws

The candidate asks how far the Erdős–Ko–Rado (EKR) property extends for independent sets of a graph that is a disjoint union of claws. For a graph $G$, let $\mathcal{I}^{(r)}(G)$ be the family of independent $r$-vertex sets; $G$ is $r$-EKR if no pairwise-intersecting subfamily of $\mathcal{I}^{(r)}(G)$ is larger than the largest star of independent $r$-sets containing one fixed vertex. Feghali, Hurlbert and Kamat (Discrete Mathematics, 2020) proved that the disjoint union $nP_3$ of $n$ paths of length 2 is $r$-EKR for $1\le r\le n/2$ — exactly the range of the Holroyd–Talbot conjecture — and posed two questions that remain open: show that for $k\ge 3$ and $2r\le n$ the disjoint union of $n$ $k$-claws $K_{1,k}$ is $r$-EKR (their Problem 1), and show that $nP_3$ is $r$-EKR for all $r\le n$, beyond the proven range (their Conjecture 1).

Background

The classical Erdős–Ko–Rado theorem (1961) states that if $n\ge 2r$, a family of pairwise-intersecting $r$-element subsets of an $n$-element set has size at most $\binom{n-1}{r-1}$, the size of a star — the family of all $r$-sets containing one fixed element. The graph-theoretic analogue studies independent sets: for a graph $G$, let $\mathcal{I}^{(r)}(G)$ be the family of independent sets of size $r$ (sets of vertices spanning no edge); the $r$-star at a vertex $v$ is the subfamily of independent $r$-sets containing $v$; and $G$ is called $r$-EKR if every intersecting subfamily of $\mathcal{I}^{(r)}(G)$ is at most as large as the largest $r$-star. Taking $G$ edgeless recovers the original theorem. Holroyd and Talbot conjectured (Discrete Mathematics, 2005) that $G$ is $r$-EKR whenever $r\le\mu(G)/2$, where $\mu(G)$ — the independent domination number — is the minimum size of a maximal independent set of $G$; this range is best possible in general. The first nontrivial case, the perfect matching $nK_2$, is equivalent (choosing one of the two endpoints of each of $r$ edges) to the EKR theorem for signed sets proved by Bollobás and Leader. Hurlbert and Kamat verified the conjecture for chordal graphs (graphs in which every induced cycle is a triangle) containing an isolated vertex; disjoint unions of claws have no isolated vertex, so these results do not apply. Feghali, Hurlbert and Kamat (Discrete Mathematics, 2020) settled the next case: the disjoint union $nP_3$ of $n$ paths of length 2 (paths on three vertices) is $r$-EKR for $1\le r\le n/2$ — exactly the Holroyd–Talbot range, since $\mu(nP_3)=n$ (taking the middle vertex of each path gives a minimum maximal independent set). Their proof introduces a probabilistic extension of Katona's cycle method, needed because $nP_3$ is not vertex-transitive: the middle vertices and the leaves behave differently, and a single component can contribute up to two vertices (both leaves) to an independent set. They close the paper with the questions that form the present problem, built on the $k$-claw — the star $K_{1,k}$, i.e. the tree whose root has degree $k$ and whose $k$ other vertices are leaves; a 2-claw is precisely a path of length 2. For the disjoint union $nK_{1,k}$ one has $\alpha(nK_{1,k})=nk$ (all leaves) and $\mu(nK_{1,k})=n$ (all roots). A positive answer would also extend the known verifications of Chvátal's 1974 conjecture — that every hereditary family $\mathcal{H}\subseteq 2^{[n]}$ (one closed under taking subsets) has no intersecting subfamily larger than its largest star — since $\mathcal{I}^{(\le r)}(G)$, the independent sets of size at most $r$, is hereditary, and Feghali–Hurlbert–Kamat observed that their theorem implies Chvátal's conjecture for these families in the range $r\le n/2$. Both questions are recorded as open in Hurlbert's survey of the Holroyd–Talbot conjecture (arXiv:2501.16144).

Problem Statement

The problem, posed in the concluding section of Feghali–Hurlbert–Kamat (2020), is to establish the Erdős–Ko–Rado property for independent sets of disjoint unions of claws, in two linked regimes that share one objective — determining how far the star property extends for these graphs. (i) Problem 1 of the source: prove that for all integers $k\ge 3$, $n\ge 1$, and $r\ge 1$ with $2r\le n$, the vertex-disjoint union $nK_{1,k}$ of $n$ $k$-claws is $r$-EKR, i.e. every pairwise-intersecting subfamily of $\mathcal{I}^{(r)}(nK_{1,k})$ has size at most $\max_v|\{S\in\mathcal{I}^{(r)}(nK_{1,k}): v\in S\}|$. This is exactly the Holroyd–Talbot range $r\le\mu(nK_{1,k})/2=n/2$ for claws with $k\ge 3$ leaves. (ii) Conjecture 1 of the source: prove that for all $n\ge 1$ and integers $1\le r\le n$, the vertex-disjoint union $nP_3$ of $n$ paths of length 2 is $r$-EKR, extending the proven range $r\le n/2$; the source notes that the bound on $r$ in its Theorem 1 is 'probably not optimal', which motivates this conjecture. A refutation of either component by an explicit intersecting family of independent $r$-sets larger than every $r$-star, at parameters in the stated ranges, is an equally admissible resolution of that component. A positive resolution of both components would also extend the verification of Chvátal's conjecture to the hereditary families $\mathcal{I}^{(\le r)}$ of these graphs.

References

1. P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics 12 (1961), 313–320. DOI: 10.1093/qmath/12.1.313. https://doi.org/10.1093/qmath/12.1.313
2. G. Katona, A simple proof of the Erdős-Chao Ko-Rado theorem, Journal of Combinatorial Theory, Series B 13 (1972), 183–184. DOI: 10.1016/0095-8956(72)90054-8. https://doi.org/10.1016/0095-8956(72)90054-8
3. F. C. Holroyd, J. Talbot, Graphs with the Erdős–Ko–Rado property, Discrete Mathematics 293 (2005), 165–176. DOI: 10.1016/j.disc.2004.08.028. https://doi.org/10.1016/j.disc.2004.08.028
4. B. Bollobás, I. Leader, An Erdős-Ko-Rado theorem for signed sets, Computers & Mathematics with Applications 34 (1997), no. 11, 9–13. DOI: 10.1016/S0898-1221(97)00215-0. https://doi.org/10.1016/S0898-1221(97)00215-0
5. G. Hurlbert, V. Kamat, Erdős–Ko–Rado theorems for chordal graphs and trees, Journal of Combinatorial Theory, Series A 118 (2011), no. 3, 829–841. DOI: 10.1016/j.jcta.2010.11.017. https://doi.org/10.1016/j.jcta.2010.11.017
6. V. Chvátal, Intersecting families of edges in hypergraphs having the hereditary property, Hypergraph Seminar, Lecture Notes in Mathematics 411 (1974), 61–66. DOI: 10.1007/BFb0066179. https://doi.org/10.1007/BFb0066179
7. C. Feghali, M. Johnson, D. Thomas, Erdős–Ko–Rado theorems for a family of trees, Discrete Applied Mathematics 236 (2018), 464–471. DOI: 10.1016/j.dam.2017.10.009. https://doi.org/10.1016/j.dam.2017.10.009
8. Carl Feghali, Glenn Hurlbert, Vikram Kamat, An Erdős–Ko–Rado theorem for unions of length 2 paths, Discrete Mathematics 343 (2020), no. 12, 112121. DOI: 10.1016/j.disc.2020.112121; arXiv:1910.08849. https://arxiv.org/abs/1910.08849 (source of Conjecture 1 and Problem 1)
9. Peter Frankl, Glenn Hurlbert, On the Holroyd-Talbot conjecture for sparse graphs, Discrete Mathematics 347 (2024), no. 1, 113742. DOI: 10.1016/j.disc.2023.113742. https://doi.org/10.1016/j.disc.2023.113742
10. Melissa M. Fuentes, Vikram Kamat, On intersecting families of subgraphs of perfect matchings, Discrete Mathematics 348 (2025), no. 7, 114460. DOI: 10.1016/j.disc.2025.114460; arXiv:2407.12289. https://arxiv.org/abs/2407.12289
11. Glenn Hurlbert, A Survey of the Holroyd-Talbot Conjecture, arXiv:2501.16144 (2025); published in Bolyai Society Mathematical Studies (2026), 183–201. DOI: 10.1007/978-3-032-18810-6_10. https://arxiv.org/abs/2501.16144
12. Neal Bushaw, James Danielsson, Glenn H. Hurlbert, Erdős-Ko-Rado Theorems for Paths in Graphs, arXiv:2504.05406 (2025). https://arxiv.org/abs/2504.05406
13. Karen Gunderson, Karen Meagher, Joy Morris, Venkata Raghu Tej Pantangi, Hilton-Milner Theorem for the r-independent sets in a union of cliques, arXiv:2511.18785 (2025). https://arxiv.org/abs/2511.18785