no. 7 · Tuesday 3 November 2026
The Erdős–Hajnal property for paths
Abstract
The well-known Erdős-Hajnal conjecture states that for any graph $H$, there is a constant $c=c(H)>0$ such that every $n$-vertex graph $G$ with no induced copies of $H$ contains a clique or an independent set of size at least $n^{c}$. In this paper, we prove that the Erdős-Hajnal conjecture holds for every path.
- comments
- 28 pages, 1 figure
- fields
- Combinatorics