Holroyd–Talbot conjecture on the EKR property of graphs
Holroyd–Talbot conjecture on the EKR property of graphs
Let be a graph, let denote the family of independent -subsets of , and let denote the star centered at . Write for the size of a smallest maximal independent set of . A graph is -EKR if there is a vertex such that every intersecting family satisfies . Holroyd–Talbot conjecture. Every graph is -EKR whenever
This conjecture extends the Erdős–Ko–Rado theorem from uniform set systems to independent sets in graphs. It asserts that the threshold for the EKR property is governed by the minimum size of a maximal independent set; its general status is not specified in the source.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Zaphenath Joseph, “An EKR Theorem for the Cartesian Product of Complete Graphs”, arXiv:2509.14291 (2025).
Additional references
9 papers in this index state this conjecture (2009–2025). The statement above is taken from the most recent of them; the others are arXiv:2501.16144, arXiv:2207.01661, arXiv:2106.09067, arXiv:2009.00732, arXiv:1610.08153, arXiv:1506.07741, arXiv:1001.0313, arXiv:0903.4203.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.